C++: Three Sum

Thought Process

The Three Sum problem can be solved efficiently using a two-pointer approach. First, sort the array to make it easier to handle duplicates and to use the two-pointer technique. Iterate through the array, and for each element, use two pointers to find pairs that sum up to the negative of the current element, ensuring that the sum of all three elements is zero. Skip duplicates to avoid redundant solutions. This approach ensures that we find all unique triplets that sum to zero. 

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
          
        sort(nums.begin(),nums.end());
        vector<vector<int>> ans;
        vector<int> tmp;
        for(int i=0;i<nums.size()-2;i++){
  
            if(i>0 && nums[i]==nums[i-1])
                continue;
  
            int j = i+1;
            int k = nums.size()-1;
  
            while(j<k){
  
                int sum = nums[i]+nums[j]+nums[k];
                if(sum==0){
                    tmp.clear();
                    tmp.push_back(nums[i]); tmp.push_back(nums[j]); 
                    tmp.push_back(nums[k]);
                    ans.push_back(tmp); 
                    // We can also use binary Search (or count) 
                    // to check whether tmp is already present inside ans vector. 
  
                    while(j<k && nums[j]==nums[j+1])
                        j++;
  
                    while(j<k && nums[k]==nums[k-1])
                        k--;
  
                    j++;
                    k--;
                }
                else if(sum<0){
                    j++;
                }
                else{
                    k--;
                }
            }
        }
        return ans;
    }
};

Code Complexity

Time Complexity: O(n2)

The algorithm iterates through the array once, and for each element, it uses a two-pointer approach to find pairs, resulting in a time complexity of O(n2).

Space Complexity: O(1)

The algorithm uses a constant amount of extra space, ignoring the space required for the output.

Code copied!