Problems statement
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Sample Test Cases
Given array nums = [-1, 0, 1, 2, 2, -4], A solution set is: [ [-4, 2, 2], [-1, 0, 1] ]
Problem Solution
We Solve this question by fixing the first element and then finding the other two using two pointer algorithm.
So first we sort the array in ascending order and Traverse it from start to end.
For every Index i, we create two variables l=i+1 and h= arr_size-1 . Then we run the loop until l is less than h , if sum of nums[l] and nums[h] is equal to zero then store the triplet.
If the sum is less than zero then we increment value of l, since array is sorted increasing value of l leads to increase in sum as nums[l+1]>nums[l].
If sum is greater than zero then we decrement the value of h, by decreasing value of h the overall sum value decreases as nums[h-1]<nums[h].
Complexity Analysis
- Time Complexity: O(n^2).only two nested loops are required, so the time complexity is O(n2).
- Space Complexity: O(1), no extra space is required, so the time complexity is constant.
Code Implementation
// C++ program to find a triplet
#include <bits/stdc++.h>
using namespace std;
void threeSum(vector<int>nums,int sum)
{ int arr_size= nums.size();
int l, r;
vector< vector<int> > result;
/* Sort the elements */
sort(nums.begin(), nums.end());
/* Now fix the first element one by one and find the
other two elements */
vector<int> temp;
for (int i = 0; i < arr_size - 2; i++) {
// To find the other two elements, start two index
// variables from two corners of the array
l = i + 1;
temp.clear();
r = arr_size - 1; // index of the last element
while (l < r) {
if (nums[i] + nums[l] + nums[r] == sum) {
temp.push_back(nums[i]);
temp.push_back(nums[l]);
temp.push_back(nums[r]);
l++;
r--;
result.push_back(temp);
temp.clear();
}
else if (nums[i] + nums[l] + nums[r] < sum)
l++;
else // A[i] + A[l] + A[r] > sum
r--;
}
}
for(int i=0;i<result.size();i++)
{
for(int j=0;j<3;j++)
{
cout<<result[i][j]<<" ";
}
cout<<endl;
}
}
/* Driver program to test above function */
int main()
{
vector<int> nums ;
nums.push_back(-1);
nums.push_back(0);
nums.push_back(1);
nums.push_back(2);
nums.push_back(2);
nums.push_back(-4);
int sum = 0;
threeSum(nums,sum);
return 0;
}
