DEV Community 👩‍💻👨‍💻

Mayank Arora
Mayank Arora

Posted on

15. 3Sum [Leetcode][C++]

All suggestions are welcome. Please upvote if you like it. Thank you.


Leetcode Problem Link: 15. 3Sum


Brute Force Solution:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // Brute Force Solution Time O(N^3) & Auxiliary Space O(1)
        int len=nums.size();
        if(len==0 || len<3) // Atleast three elemnets needed for a triplet
            return {};
        set<vector<int>> s; // Set stores unique elements only(duplicate triplets not added)
        sort(nums.begin(),nums.end());
        // Compare all cases of group of three elements for their sum=0 in O(N^3) time
        for(int i=0;i<len-2;i++){
            for(int j=i+1;j<len-1;j++){
                for(int k=j+1;k<len;k++){
                    if(nums[i]+nums[j]+nums[k]==0){
                        s.insert({nums[i],nums[j],nums[k]});
                    }
                }
            }
        }
        // Insert all unique triplets in result vector
        vector<vector<int>> ans(s.begin(),s.end());
        return ans;
    }
};

Enter fullscreen mode Exit fullscreen mode

Efficient Solution:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums){
        // Optimal Solution Time O(N^2) & Auxiliary Space O(1)
        // Two Pointer Algorithm
        int len=nums.size();
        vector<vector<int>> res;
        if(len<3)
            return res;
        sort(nums.begin(),nums.end());
        for(int i = 0; i<len; i++){
            if(i>0 && nums[i]==nums[i-1])
                // Skip the duplicate elements by incrementing the i index.
                // 'continue' terminates current iteration and
                // begins next iteration of for loop
                continue; 
            // Keeping nums[i] same, check for sum of triplets=0 
            // from i+1 till the end of nums vector
            int left = i + 1, right = nums.size() - 1; 
            while(left<right) 
            {    
                if(nums[i] + nums[left] + nums[right] == 0){
                    res.push_back(vector<int>{nums[i],nums[left],nums[right]});
                    // To skip duplicate elements at left pointer
                    while(left<right && nums[left]==nums[left+1]) 
                        left++;
                    // To skip duplicate elements at left pointer
                    while(left<right && nums[right]==nums[right-1]) 
                        right--;
                    // One unique triplet has been found.
                    // Increment left & decrement right for  
                    // next triplet to be unique
                    left++;
                    right--;
                }
                // Since nums is sorted, so left will be smallest in 
                // [nums[left],nums[right]] interval and if triplet sum<0,
                // then incrementing left will increase the sum
                else if(nums[i]+nums[left]+nums[right]<0) 
                    left++; 
                // Since nums is sorted, so right will be largest in 
                // [nums[left],nums[right]] interval and if triplet sum>0,
                // then decrementing right will decrease the sum
                else
                    right--; 
            }

        }
        return res;
    }
};
Enter fullscreen mode Exit fullscreen mode

All suggestions are welcome. Please upvote if you like it. Thank you.

Top comments (0)

Regex for lazy developers

regex for lazy devs

You know who you are. Sorry for the callout 😆