3 SUM LeetCode Solution: Hello geeks😁, in this article we are going to discuss the 3 sum problem on LeetCode.
We would be discussing:
- Problem statement
- Different approaches
- Time complexity
- Space complexity
Understanding the problem statement
Given statement: Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]]
Example 2:
Input: nums = [] Output: []
Example 3:
Input: nums = [0] Output: []
Constraints:
0 <= nums.length <= 3000-105 <= nums[i] <= 105
Explanation: In this problem we are given an array nums of n integers and we have to find all the unique triplets in the array whose summation gives 0. Consider the above example 1 in which we are given an array nums = [-1,0,1,2,-1,-4] we can clearly observe that if we take [-1,0,1] the resultant would be 0 so it is a desired triplet. Also [-1,-1,2] will be the desired triplet. Since no more triplets are possible so now we would be returning our answer set which would be like [[-1,0,1],[-1,-1,2]].
The constraints here also tell that the given integer array would have elements ranging from -105 to 105 and its length won’t exceed 3000.
How to approach 3 Sum Leetcode Solution?
The above given problem can be solved in multiple ways
1) Brute Force
The naive approach to solve the 3 sum problem would be to iterate over every element and check for triplets. We would be using 3 for loops here and will iterate through all the elements of the array and check for all the possible combination. We have to keep in mind that we don’t want duplicates so we would be using set to store the values then we can restore it in the required format i.e. vector of vectors.
Algorithm:
- Take 3 nested for loops
- Run the first loop from the start to the end, the second loop will be running from j=i+1 to the end, and the third loop will run from k=j+1 to end.
- The elements at these 3 indexes will be the triplets.
- Check the condition a+b+c==0 for every combination possible.
- Store the desired combinations in a set.
- Store the values of set in a vector and return it as the answer.
C++ Code
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>>s;
int n= nums.size();
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
for(int k=j+1;k<n;k++)
{
if(nums[i]+nums[j]+nums[k]==0)
{
vector<int>v(3);
v[0]=nums[i];v[1]=nums[j];v[2]=nums[k];
sort(v.begin(),v.end());
s.insert(v);
}
}
}
}
vector<vector<int>>v;
for(auto i:s)
{
v.push_back(i);
}
return v;
}
};This approach would be giving a Time Limit Exceeded error.
Time Complexity: The time complexity of the above approach is O(n3)(log m)
Space Complexity: The space complexity of the above algorithm is O(m)
2) Using Hash Map/ Hash Table
A better solution to the 3 sum problem is by using Hashing we would be iterating over the array of integers by using two nested for loops. The two for loops will give us the values of a and b. But here, instead of using a third for loop we can extract the value of c from the hash table in which we would be storing elements along with there occurrence in the array.
Here we have to keep in mind that we don’t have to consider the same element more than once in a triplet so we would be decrementing the frequency of the element used for a and b from the hash map.
Algorithm:
- Iterate over the input array to store the values in a hash map.
- Run two nested for loops first from i=1 to n. Second from j=i+1 to n. The elements at the two indexes will be corresponding to the two elements of the triplet.
- a+b+c=0 so c=-(a+b). Use the hash map to find this value.
- Store the desired combinations in a set.
- Store the values of set in a vector and return it as the answer.
C++ code
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>>s;
unordered_map<int,int> m;
int n= nums.size();
for(int i=0;i<n;i++)
{
m[nums[i]]++;
}
for(int i=0;i<n;i++)
{
m[nums[i]]--;
for(int j=i+1;j<n;j++)
{
m[nums[j]]--;
int c = -1*(nums[i]+nums[j]);
if(m.find(c) != m.end() && m[c]>0)
{
vector<int>v(3);
v[0]=nums[i],v[1]=nums[j],v[2]=c;
sort(v.begin(),v.end());
s.insert(v);
}
m[nums[j]]++;
}
m[nums[i]]++;
}
vector<vector<int>>v;
for(auto i:s)
{
v.push_back(i);
}
return v;
}
};The above approach will give a Time limit Exceeded error.
Time Complexity: The time complexity of the above approach is O(n2 logm).
Space Complexity: The space complexity of the above approach is O(n).
3) Two Pointer approach
The best method to get 3 SUM LeetCode Solution would be using two pointers approach.
Here the first step would be to sort the given input array. We would also get rid of the extra space that we were using.
We know that a+b+c=0. If we keep ‘a’ constant we will get b+c=-a. We can now get b and c using the two pointer approach. Let i denote the present index of a so we will start from i+1 (low pointer) to search b and n-1(high pointer) to search for c where n is the size of nums array. If the sum of b+c is giving less than the required sum so we will just increase the low pointer one step towards right.
Also in order to ignore the duplicate triplets we will increase the low pointer until we reach a position where low is not equal to its previous value similarly we will move high until we reach a position where high is not equal to its previous value. After doing all such combination of triplets with a value of ‘a’ we will move a to a value where it is not equal to it’s previous value this is because we don’t want repetitive triplets and also we are not using a set this time.
Algorithm:
- Sort the input array.
- Iterate over the input array to fix the value of ‘a’.
- Take two pointers, one(low) at i + 1 and the other(high) at n – 1.
- If the sum is smaller than -a, shift the low pointer to right.
- Else, If the sum is bigger, shift the high pointer to the left.
- Else, if the sum of elements at two-pointer is equal then store it in vector.
- To eliminate the redundancy shift the low and high pointer unless you get a value not equal to previous value.
- Return the vector as the answer.
C++ Code
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
if(nums.size() < 3) return ans;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size()-2; i++){
if(i == 0 || nums[i-1] != nums[i]){
int low = i+1, high = nums.size()-1, sum = -nums[i];
while(low < high){
if(nums[low] + nums[high] == sum){
ans.push_back({nums[i], nums[low], nums[high]});
while(low < high && nums[low] == nums[low+1])
low++;
while(low < high && nums[high] == nums[high-1])
high--;
low++;
high--;
}
else if(nums[low] + nums[high] < sum){
low++;
}
else{
high--;
}
}
}
}
return ans;
}
};Time Complexity: The time complexity of the above algorithm is O(n2).
Space Complexity: The space complexity used here is O(m) but since it’s used for storing the answers it’s not calculated in the space complexity. So the space complexity is O(1).
Frequently Asked Questions
1) How does 3 sum work?
Ans) In 3 sum we have to find all sets of triplets in the array so that there sum meets the given sum.
2) What is a 2 sum?
Ans) 2 sum is a problem in which we have two find all the sets of duplet so that there sum meets the given sum.
3)What is 2 pointer approach?
Ans) 2 pointer approach is a simple and efficient approach to find the required pairs in the array.
Conclusion
In this tutorial we got the 3 SUM LeetCode Solution . We used different approaches to solve the problem.
- Brute Force
- Hash Map
- Two Pointers
Every approach was simple and easy to understand. A large scale of problems can be solved using the above approaches.
Also read : A Complete Roadmap to Competitive Programming 2022
