Three Sum is a problem loved by interviewers. It is a problem I was personally asked during the Amazon interview. So, without wasting any more time let us get to the problem. An array that has both positive and negative numbers. Three numbers that sum up to zero/can be modified, to sum up to any integer or find three-element from different three arrays such that a + b + c = sum.
Table of Contents
Example
Input
[-2,0,1,1,2]
Output
[[-2,0,2],[-2,1,1]]
How to solve it?
Before it becomes a bigger pain for my readers. Let me run through small pseudocode illustrating the same. Step By Step:
- Firstly sort the numbers.
- Sorting helps us access the digits as per their magnitude.
- Secondly, we select an element from the array.
- Thirdly we select two elements who on summing up with the first element will yield zero.
- In case you are having a Deja Vu let me drop a hint.
- The TWO SUM problem.
- Once we fix the first element we run over the array to find the other two elements.
- We take two ends.
- Every time the sum from the two ends is grater than desired we decrement the end value.
- Every time the sum from the two ends is lesser than desired we increment the start value.
- If the sum reaches 0 we record the elements.
- Lastly, the elements are added to an ArrayList of the set to ensure that there is no repetition.
Java Code for Three Sum
class Solution
{
public List<List<Integer>> threeSum(int[] nums)
{
Arrays.sort(nums);
if(nums.length<3)
return new ArrayList<>();
Set<List<Integer>>lisa=new HashSet<>();
for(int i=0;i<nums.length;i++)
{
int start=i+1;
int end=nums.length-1;
while(end>start)
{
int sum=nums[i]+nums[start]+nums[end];
if(sum==0)
{
List<Integer>cur=new ArrayList<Integer>();
cur.add(nums[i]);
cur.add(nums[start]);
cur.add(nums[end]);
lisa.add(cur);
end--;
start++;
}
else if(sum>0)
end--;
else if(sum<0)
start++;
}
}
return new ArrayList<>(lisa);
}
}C++ Code for Three Sum
class Solution
{
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
sort(nums.begin(),nums.end());
vector<vector<int>>ans;
set<vector<int>>lisa;
for(int i=0;i<nums.size();i++)
{
int start=i+1;
int end=nums.size()-1;
while(end>start)
{
int sum=nums[i]+nums[start]+nums[end];
if(sum==0)
{
lisa.insert({nums[i],nums[start],nums[end]});
end--;
start++;
}
else if(sum>0)
end--;
else if(sum<0)
start++;
}
}
for(auto x:lisa)
{
ans.push_back(x);
}
return ans;
}
};Complexity Analysis
Time Complexity=O(n^2)
Space Complexity=O(1)
How?
Time Complexity Analysis For Three Sum
- Firstly, we run through the outer loop once finding the first element we can fix.
- The inner loop.
- Takes the first element.
- Takes the second element from the end.
- In the worse case, we might start moving from the first element to the last element.
- Which leads to the time complexity of O(n^2)
Space Complexity Analysis For Three Sum
- We only use a few variables to keep track.
- Thus, leading up the space complexity to O(1)
A Small Tweak
What if we change the Three Sum problem’s storage units. Amazed!?
Nothing much. We will just take up three different arrays than a single one. In case you still did not get it. Let me present a sample test case.
Input
Array1= { 1 , 2 , 3 , 4 , 5 }
Array2= { 2 , 3 , 6 , 1 , 2 }
Array3= { 3 , 2 , 4 , 5 , -6 }
Output
YES
Here is an image highlighting the possible triplets
How to Approach The Problem
- Firstly, we try to generate all possible combinations of the sum from any two arrays.
- To achieve this we run two loops
- We store all these combinations in a set to avoid repetitions
- We check if the -ve value of the sum is available in the third array
- If yes then we return yes
- Lastly even after looping through all arrays if we do not achieve 0 then we return false
Java Code for Three Sum
public class Main
{
public static boolean Three(int a1[],int a2[],int a3[])
{
Set<Integer>store=new HashSet<Integer>();
Set<ArrayList<Integer>>lisa=new HashSet<>();
for(int i=0;i<a2.length;i++)
{
for(int j=0;j<a3.length;j++)
store.add(a2[i]+a3[j]);
}
for(int i=0;i<a1.length;i++)
{
if(store.contains(-a1[i]))
{
return true;
}
}
return false;
}
public static void main (String[] args)
{
int a1[] = { 1 , 2 , 3 , 4 , 5 };
int a2[] = { -2 , 3 , 6 , 1 , 2 };
int a3[] = { 3 , 2 , -4 , 5 , -6 };
int n1 = a1.length;
int n2 = a2.length;
int n3 = a3.length;
System.out.println(Three(a1, a2, a3));
}
}C++ Code for Three Sum
bool Three(int a1[],int a2[],int a3[])
{
int n1 = sizeof(a1) / sizeof(a1[0]);
int n2 = sizeof(a2) / sizeof(a2[0]);
int n3 = sizeof(a3) / sizeof(a3[0]);
set<int>store;
for(int i=0;i<n2;i++)
{
for(int j=0;j<n3;j++)
store.insert(a2[i]+a3[j]);
}
for(int i=0;i<n1;i++)
{
if(store.find(-a1[i])!=store.end())
{
return true;
}
}
return false;
}
int main()
{
int a1[] = { 1 , 2 , 3 , 4 , 5 };
int a2[] = { 2 , 3 , 6 , 1 , 2 };
int a3[] = { 3 , 2 , 4 , 5 , 6 };
cout<<Three(a1, a2, a3);
return 0;
}Complexity Analysis
Time Complexity=O(n^2)
How?
- We run an outer loop to find the element from the second array.
- In the inner loop, we add an element from the third array to the second array element.
- The time complexity incurred till now is O(n^2).
- The next loop checks element from the first array
- The time complexity for this loop=O(1)
- Final complexity till now=O(n^2)+O(1)=O(n^2)
Space Complexity=O(n)
How?
- We use a set to store all the elements
- This leads to time complexity of O(n)