Triplet Sum In An Array
Introduction
Triplet Sum is a common interview question asked in many companies like Accolite, Amazon, OYO rooms, Samsung, Microsoft.
Triplet Sum is an extension of Two Sum Problem based on Binary Search.
Problem Statement
Given an array of integers, write a program to find the distinct triplets which sum up to a given value ‘K’.
Example
Input:
10 5 5 5 2
12
Output:
5 5 2
Explanation:
5 5 2 is the only triplet to form sum equal to 12
Input:
1 2 3 1 2 3
6
Output:
1 2 3
Explanation:
1 2 3 is the only unique triplet to form sum equal to 6
Let us now discuss the approaches for the Triplet sum in array.
Approach: 1
The first approach for the Triplet Sum problem is as follows.
Find all the triplets of the array and count all the triplets that give sum=k.
Three nested loops for three different indexes to check the values at those indexes sum up to ‘K’.
Make a set to keep track of the visited triplets.
If the triplet is not found in thes set then print the triplet else continue.
Code:
// Program to find triplet sum
#include<set>
vector<vector<int>> findTriplets(vector<int>arr, int n, int K) {
// Set to keep the track of visited triplets.
set<vector<int>>visited;
vector<vector<int>>ans;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
// If we find a valid triplet.
if (arr[i] + arr[j] + arr[k] == K) {
vector<int> triplet;
triplet.push_back(arr[i]);
triplet.push_back(arr[j]);
triplet.push_back(arr[k]);
// Sorting the triplet track distinct triplets.
sort(triplet.begin(), triplet.end());
if (visited.find(triplet) == visited.end()) {
ans.push_back(triplet);
visited.insert(triplet);
}
}
}
}
}
return ans;
}
Time Complexity
O(n ^ 3), where n is the length of the array.
As three nested for loop traverses from 0 to n-1.
Space Complexity
O(1)
As we are using constant memory space.
Approach: 2
The second approach for the Triplet Sum problem is as follows.
Sort the array to not process the same elements multiple times.
Let triplets be ‘x’, ‘y’, ‘z’.
x+y+z = k. So, y+z = k-x in which we can fix x = arr[i]. Hence, we need to find the sum of two numbers whose sum = k-arr[i].
Make a for loop from 0 to n with iterator ‘i’.
Find the two numbers which make the sum of ‘target’ = k-arr[i].
Make two pointers x and y pointing to i+1 and n-1 respectively.
While x<y
Make a variable ‘sum’ = arr[x] + arr[y]
If sum < target then increment x
If sum > target then decrement y
Else print the triplet and since we want distinct triplets and increment the ‘x’ pointer until the same element occurs at ‘x’ and decrement ‘y’ pointer until the same element occurs at ‘y’.
Code:
// Program to find triplet sum
vector<vector<int>> findTriplets(vector<int>arr, int n, int K) {
vector<vector<int>>ans;
// Sorting the vector.
sort(arr.begin(), arr.end());
for (int i = 0; i < n; i++) {
int target = K - arr[i];
int x = i + 1;
int y = n - 1;
while (x < y) {
int sum = arr[x] + arr[y];
// Finding an answer which starts from arr[i].
if (sum < target) {
x++;
}
else if (sum > target) {
y--;
}
else {
int a = arr[x];
int b = arr[y];
ans.push_back({arr[i], arr[x], arr[y]});
// Incrementing front pointer until we reach a different number.
while (x < y && arr[x] == a) {
x++;
}
// Decrement the last pointer until we reach a different number.
while (x < y && arr[y] == b) {
y--;
}
}
}
// Ensuring that we don't encounter duplicate values for arr[i].
while (i + 1 < n && arr[i] == arr[i + 1]) {
i++;
}
}
return ans;
}
Time Complexity
O(n ^ 2), where n is the length of the array.
As two nested for loop traverses from 0 to n-1.
Space Complexity
O(1)
As we are using constant memory space.
Comments
Post a Comment