Optimized Approach (Two Pointer)
Requirements we need to fulfil: Find the triplets having sum = 0(zero-sum).
As array has both -ve and +ve numbers, firstly we sort the array. Sorted array would have -ve numbers together and +ve numbers together in an increasing order. This will make easy for searching the required numbers to make a 0 sum.
Base cases after sorting:
- If array size is < 3, means no triplet would exist from that array. Return empty vector of vectors.
-
If first element is +ve, that means there is no -ve number by which we can make a 0 triplet sum. Return empty vector of vectors.
The basic thinking logic for this is: Fix any one number in sorted array and find the other two numbers after it. The other two numbers can be easily found using two pointers (as array is sorted) and two numbers should have sum = -1*(fixed number).
Steps of Algorithm
- Traverse the array and fix a number at every iteration.
- If number fixed is +ve, break there because we can't make it zero by searching after it.
- If number is getting repeated, ignore the lower loop and continue. This is for unique triplets. We want the last instance of the fixed number, if it is repeated.
- Make two pointers high and low, and initialize sum as 0.
- Search between two pointers, just similiar to binary search. Sum = num[i] + num[low] + num[high].
- If sum is -ve, means, we need more +ve numbers to make it 0, increament low (low++).
- If sum is +ve, means, we need more -ve numbers to make it 0, decreament high (high--).
- If sum is 0, that means we have found the required triplet, push it in answer vector.
- Now again, to avoid duplicate triplets, we have to navigate to last occurences of num[low] and num[high] respectively. Update the low and high with last occurences of low and high.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> threeSum(vector<int> &nums)
{
sort(nums.begin(), nums.end()); // Sorted Array
if (nums.size() < 3)
{ // Base case 1
return {};
}
if (nums[0] > 0)
{ // Base case 2
return {};
}
vector<vector<int>> answer;
for (int i = 0; i < nums.size(); ++i)
{ // Traversing the array to fix the number.
if (nums[i] > 0)
{ // If number fixed is +ve, stop there because we can't make it zero by searching after it.
break;
}
if (i > 0 && nums[i] == nums[i - 1])
{ // If number is getting repeated, ignore the lower loop and continue.
continue;
}
int low = i + 1, high = nums.size() - 1; // Make two pointers high and low, and initialize sum as 0.
int sum = 0;
while (low < high)
{ // Search between two pointers, just similiar to binary search.
sum = nums[i] + nums[low] + nums[high];
if (sum > 0)
{ // If sum is +ve, means, we need more -ve numbers to make it 0, decreament high (high--).
high--;
}
else if (sum < 0)
{ // If sum is -ve, means, we need more +ve numbers to make it 0, increament low (low++).
low++;
}
else
{
answer.push_back({nums[i], nums[low], nums[high]}); // we have found the required triplet, push it in answer vector
int last_low_occurence = nums[low], last_high_occurence = nums[high]; // Now again, to avoid duplicate triplets, we have to navigate to last occurences of num[low] and num[high] respectively
while (low < high && nums[low] == last_low_occurence)
{ // Update the low and high with last occurences of low and high.
low++;
}
while (low < high && nums[high] == last_high_occurence)
{
high--;
}
}
}
}
return answer; // Return the answer vector.
}
int main()
{
int n; // store the size of vector
cin >> n;
vector<int> nums(n); // vector of size n
for (int i = 0; i < n; i++)
cin >> nums[i];
vector<vector<int>> ans = threeSum(nums);
cout << "number of triplet with zero-sum: ";
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); i++)
{
for (auto element : ans[i])
cout << element << ' ';
cout << endl;
}
}
You can also try this code with Online C++ Compiler
Input:
6
-1 0 1 2 -1 -4
You can also try this code with Online C++ Compiler
Output:
number of triplet with zero-sum: 2
-1 -1 2
-1 0 1
You can also try this code with Online C++ Compiler
Complexity Analysis
Time Complexity: O(n2)
Since the approach consists of finding a pair in one loop then finding the triplet with zero sum.Therefore overall time complexity would be of order O(n2).
Space Complexity: O(1)
We Cannot uses any extra space so in worst case space coplexity is O(1).
Check out this array problem - Merge 2 Sorted Arrays
Optimized Approach (HashMap Approach)
Requirements we need to fulfil: Find the triplets having sum = 0(zero-sum).
As array has both -ve and +ve numbers, firstly we sort the array. Sorted array would have -ve numbers together and +ve numbers together in an increasing order. This will make easy for searching the required numbers to make a 0 sum.
Base cases after sorting:
- If array size is < 3, means no triplet would exist from that array. Return empty vector of vectors.
-
If first element is +ve, that means there is no -ve number by which we can make a 0 triplet sum. Return empty vector of vectors.
In this approach, firstly, we will hash the indices of all elements in a hashMap. In case of repeated elements, the last occurence index would be stored in hashMap.
Steps of Algorithm
- Here also we fix a number (num[i]), by traversing the loop. But the loop traversal here for fixing numbers would leave last two indices. These last two indices would be covered by the nested loop.
- If number fixed is +ve, break there because we can't make it zero by searching after it.
- Make a nested loop to fix a number after the first fixed number. (num[j])
- To make sum 0, we would require the -ve sum of both fixed numbers. Let us say this required.
- Now, we will find the this required number in hashMap. If it exists in hashmap and its last occurrence index > 2nd fixed index, we found our triplet. Push it in answer vector.
- Update j to last occurence of 2nd fixed number to avoid duplicate triplets.
- Update i to last occurence of 1st fixed number to avoid duplicate triplets.
- Return answer vector.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> threeSum(vector<int> &nums)
{
sort(nums.begin(), nums.end()); // Sorted Array
if (nums.size() < 3)
{ // Base Case 1
return {};
}
if (nums[0] > 0)
{ // Base Case 2
return {};
}
unordered_map<int, int> hashMap;
for (int i = 0; i < nums.size(); ++i)
{ // Hashing of Indices
hashMap[nums[i]] = i;
}
vector<vector<int>> answer;
for (int i = 0; i < nums.size() - 2; ++i)
{ // Traversing the array to fix the number.
if (nums[i] > 0)
{ // If number fixed is +ve, stop there because we can't make it zero by searching after it.
break;
}
for (int j = i + 1; j < nums.size() - 1; ++j)
{ // Fixing another number after first number
int required = -1 * (nums[i] + nums[j]); // To make sum 0, we would require the -ve sum of both fixed numbers.
if (hashMap.count(required) && hashMap.find(required)->second > j)
{ // If it exists in hashmap and its last occurrence index > 2nd fixed index, we found our triplet.
answer.push_back({nums[i], nums[j], required});
}
j = hashMap.find(nums[j])->second; // Update j to last occurence of 2nd fixed number to avoid duplicate triplets.
}
i = hashMap.find(nums[i])->second; // Update i to last occurence of 1st fixed number to avoid duplicate triplets.
}
return answer; // Return answer vector.
}
int main()
{
int n; // store the size of vector
cin >> n;
vector<int> nums(n); // vector of size n
for (int i = 0; i < n; i++)
cin >> nums[i];
vector<vector<int>> ans = threeSum(nums);
cout << "number of triplet with zero-sum: ";
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); i++)
{
for (auto element : ans[i])
cout << element << ' ';
cout << endl;
}
}
You can also try this code with Online C++ Compiler
Input:
6
-1 0 1 2 -1 -4
You can also try this code with Online C++ Compiler
Output:
number of triplet with zero-sum: 2
-1 -1 2
-1 0 1
You can also try this code with Online C++ Compiler
Complexity Analysis
Time Complexity: O(n2)
Since the approach consists of finding a pair in one loop then finding the triplet with zero sum.Therefore overall time complexity would be of order O(n2).
Space Complexity: O(n)
For storing the element in hash map.
Frequently Asked Question
What is a stack?
A stack is a linear data structure which comprises homogeneous elements and works on the principle of last in first out.That means,one which goes in last will come out first.
What is a map?
A map is like a dictionary where elements are stored in key-value manner.It stores the elements in the sorted order of keys.
What is the time complexity of push and pop operations in stack?
The time complexity of push and pop operations is O(1) since it takes a constant amount of time to either push an element in the top or pop the top element and reduce size by one.
Conclusion
This article discussed the approach to find all triplet with sum zero in array of both positive and negative value.First a brute force then we move to two optimal approach using two pointer method and hashing.
Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, Machine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problems, interview experiences, and interview bundle for placement preparations.
Nevertheless, you may consider our paid courses to give your career an edge over others!
Do upvote our blogs if you find them helpful and engaging!
Happy Learning!!
34+ registered 
