3Sum [Medium] — Sort + Two Pointer Scan

Problem Statement

Find all unique triplets in the array that give the sum of zero. (No duplicate triplets in output.)

Input: [-1,0,1,2,-1,-4] → Output: [[-1,-1,2],[-1,0,1]]

Intuition

Sort the array. Fix element i, then use two pointers j=i+1 and k=n-1 to find pairs summing to -nums[i]. Skip duplicates at all levels.

Solutions

C++

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(),nums.end());
    vector<vector<int>> res;
    for(int i=0;i<nums.size()-2;i++){
        if(i>0&&nums[i]==nums[i-1]) continue;
        int l=i+1, r=nums.size()-1;
        while(l<r){
            int s=nums[i]+nums[l]+nums[r];
            if(s==0){
                res.push_back({nums[i],nums[l],nums[r]});
                while(l<r&&nums[l]==nums[l+1])l++;
                while(l<r&&nums[r]==nums[r-1])r--;
                l++;r--;
            } else if(s<0) l++;
            else r--;
        }
    }
    return res;
}

Java

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res=new ArrayList<>();
    for(int i=0;i<nums.length-2;i++){
        if(i>0&&nums[i]==nums[i-1]) continue;
        int l=i+1, r=nums.length-1;
        while(l<r){
            int s=nums[i]+nums[l]+nums[r];
            if(s==0){
                res.add(Arrays.asList(nums[i],nums[l],nums[r]));
                while(l<r&&nums[l]==nums[l+1])l++;
                while(l<r&&nums[r]==nums[r-1])r--;
                l++;r--;
            } else if(s<0) l++; else r--;
        }
    }
    return res;
}

JavaScript

var threeSum = function(nums) {
    nums.sort((a,b)=>a-b);
    const res=[];
    for(let i=0;i<nums.length-2;i++){
        if(i>0&&nums[i]===nums[i-1]) continue;
        let l=i+1, r=nums.length-1;
        while(l<r){
            const s=nums[i]+nums[l]+nums[r];
            if(s===0){
                res.push([nums[i],nums[l],nums[r]]);
                while(l<r&&nums[l]===nums[l+1])l++;
                while(l<r&&nums[r]===nums[r-1])r--;
                l++;r--;
            } else if(s<0) l++; else r--;
        }
    }
    return res;
};

Python

def threeSum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    res = []
    for i in range(len(nums)-2):
        if i > 0 and nums[i] == nums[i-1]: continue
        l, r = i+1, len(nums)-1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s == 0:
                res.append([nums[i], nums[l], nums[r]])
                while l < r and nums[l] == nums[l+1]: l += 1
                while l < r and nums[r] == nums[r-1]: r -= 1
                l += 1; r -= 1
            elif s < 0: l += 1
            else: r -= 1
    return res

Complexity

Time: O(n²)
Space: O(1) (output excluded)