Difficulty: Medium, Asked-in: Google, Amazon, Facebook, Microsoft
Key takeaway: An excellent problem to learn problem-solving using hashing and two pointers approach.
Given an array X[] of distinct elements, write a program to find all the unique triplets in the array whose sum is equal to zero. For example, suppose such triplets in the array are X[i], X[j] and X[k] then X[i] + X[j] + X[k] = 0. Note : solution set must not contain duplicate triplets.
Examples
Input: X[] = [0, -2, 5, -3, 2], Output: [0, -2, 2], [-2, 5, -3] Explanation : The triplets with zero sum are 0 + (-2) + 2 = 0 and (-2) + 5 + (-3) = 0
Input: X[] = [-1, 0, 1, 2, -1, -4], Output: [-1, -1, 2],[-1, 0, 1]
The basic solution idea is to find out each possible triplet and check whether their sum is equal to zero or not. We can implement this using three nested loops.
Solution Pseudocode C++
vector<vector<int>> findTripletSum(vector<int>& X)
{
vector<vector<int>> output
int n = X.size()
if(n <=2)
return output
for(int i = 0; i < n - 2; i = i + 1)
{
for(int j = i + 1; j < n - 1; j = j + 1)
{
for(int k = j + 1; k < n; k = k + 1)
{
if(X[i] + X[j] + X[k] == 0)
{
vector<int> triplet = {X[i], X[j], X[k]}
output.push_back(triplet)
}
}
}
}
return output
}
Time and space complexity analysis
Solution Idea
The previous approach works very slow because of O(n³) Time Complexity. This can be optimized to work with less time complexity using a hash table. The idea is to traverse the array and for every element X[i], we find a pair with a sum equal to – X[i]. In other words, we explore every pair of elements (X[i], X[j]) using nested loops and search for the value -(X[i] + X[j]) in the hash table.
Solution Steps
Inside the inner loop, we create a hash set to track the element with the sum = -(X[i] + X[j]).
Solution Pseudocode C++
vector<vector<int>> findTripletSum(vector<int>& X)
{
vector<vector<int>> output
int n = X.size()
if(n <=2)
return output
for (int i = 0; i < n - 1; i = i + 1)
{
unordered_set<int> s
for (int j = i + 1; j < n; j = j + 1)
{
int sum = - (X[i] + X[j])
if (s.find(sum) != s.end())
{
vector<int> triplet = {sum, X[i], X[j]}
output.insert(triplet)
}
else
s.insert(X[j])
}
}
return output
}
Time and space complexity analysis
Time Complexity is O (n²) since the algorithm is using two nested loops and space complexity is O(n), for hash-map.
Solution Idea
The previous approach requires an extra space because of the hash table. This can be further optimized to work with constant space using two pointer approach.
The idea is to first sort the array and traverse the array from left to right. Now for each element X[i], we use two pointers l (initialized with i + 1) and r (initialized with n - 1) and run a loop until r > l to find out if there are any triplets (X[i], X[l], X[r]) having a sum equal to zero is present or not.
In another way: we sort an input array and run through all indices of a possible first element of a triplet. For each possible first element, we use a bi-directional two-pointers approach similar to the pair sum problem in the remaining part of the array.
Solution Steps
Solution Pseudocode C++
vector<vector<int>> findTripletSum(vector<int>& X)
{
int n = X.size()
sort(X.begin(), X.end())
vector<vector<int>> output
if(X.size() <= 2)
return output
for(int i = 0; i < n - 2; i = i + 1)
{
int l = i + 1, r = n - 1
while(r > l)
{
int sum = X[i] + X[l] + X[r]
if(s > 0)
r = r - 1
else if(sum < 0)
l = l + 1
else
{
vector<int> triplet = {X[i], X[l], X[r]}
output.push_back(triplet)
l = l + 1
r = r - 1
}
}
}
return output
}
Time and space complexity analysis
Enjoy learning! Enjoy Algorithms!
Get well-designed application and interview centirc content on ds-algorithms, machine learning, system design and oops. Content will be delivered weekly.