Question : You are given an array . You need to return all the unique triplets which sums to zero .
Example :
Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]]
Brute Solution :
To get the solution , we can try out all the triplets.We can generate all the triplets and can check if its sum is equal to zero . To get only the unique sets we can use hashset data structure which only stores the unique triplets .
To generate all the triplets we can use three loops.Our first loop will run from i=0 to n-1 , second loop : j=i+1 to n-1 and third loop from k=j+1 to n-1.
Pseudo Code :
for(i=0 to n-1){
for(j=i+1 to n-1){
for(k=j+1 to n-1){
if(arr[i]+arr[j]+arr[k]==0){
s.insert({arr[i],arr[j],arr[k]})
}
}
}
Optimal Solution :
We can use two pointer approach to solve this problem .In this problem what we actually require is a+b+c=0 . Now here we can consider a as constant , in that case we can actually write b+c=-a ,Now we need to find b and c , using two pointers technique .
To find b and c , first we are going to sort the array .After that we will take one element as constant and next of it as our one pointer and end of the array as our another pointer . Now we will be finding two element which sums to negative of our constant element . Example :
nums = [-1,0,1,2,-1,-4] After sorting , nums=[-4,-1,-1,0,1,2] so we will take , -4 as our constant , we will keep our first pointer at -1 and last pointer at 2 , we will be iterating between -1 to 2 using two pointers to find -(-4) by adding up two elements between two pointers.
The we will choose -1(1st index) as our constant and will keep two pointers at -1(2nd index) and 2, and try finding b and c such that b+c=-(-1).
Lets denote our first pointer as b and last pointer as c which is at end of array . Now we need to think how we gonna move our pointer .So if b+c < -a , the we will move b as b++ and if b+c>-a we will move c ie c–.And if it equals then we will do both that is b++ and c–.
Now we need to think about duplicate triplets . To avoid duplicate triplets when we hit our desire target we will move b and c as long as we dont get an unique element.We will do this in following way :
while (a < b && nums[a] == nums[a+1]) a++;
while (a < b && nums[b] == nums[b-1]) b–;
In this way after completing the above approach we will have all our required triplets.
Code :
C++ :
Function to find triplets :
vector<vector<int>> threeSum(vector<int>& nums) {
int n=nums.size();
vector<vector<int>>ans;
sort(nums.begin(),nums.end());
for(int i=0;i<n-2;i++)
{
int a=i+1;
int b=n-1;
int target=-nums[i];
while(a<b)
{
if(nums[a]+nums[b]<target)
{
a++;
}
else if(nums[a]+nums[b]>target)
{
b--;
}
else
{
vector<int>v(3,0);
v[0]=nums[i];
v[1]=nums[a];
v[2]=nums[b];
ans.push_back(v);
while (a < b && nums[a] == nums[a+1]) a++;
while (a < b && nums[b] == nums[b-1]) b--;
a++;
b--;
}
}
while(i+1<n and nums[i]==nums[i+1])i++;
}
return ans;
}
Time Complexity : O(nxn)
Space Complexity : O(m) , space to store the triplets
Leave a Reply