3Sum — Sort + Two Pointers O(n²) Deduplication [Google, Meta, Amazon]

Problem Statement

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j != k and nums[i] + nums[j] + nums[k] == 0. No duplicate triplets.

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

Intuition
C++ Solution
Java Solution
Python Solution
JavaScript Solution
Complexity: O(n²) time, O(1) extra space (excluding output)

Intuition

Sort the array. Fix element at index i. Use two pointers l=i+1 and r=n-1 to find pairs summing to -nums[i]. Skip duplicates after each find.

sort(nums)
for i = 0..n-3:
    if nums[i] > 0: break  // sorted, no triple can sum to 0
    if i > 0 and nums[i] == nums[i-1]: skip  // deduplicate i
    l, r = i+1, n-1
    while l < r:
        s = nums[i]+nums[l]+nums[r]
        if s == 0: record, skip dups on l and r
        elif s < 0: l++
        else: r--

C++ Solution

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        int n = nums.size();
        for (int i = 0; i < n-2; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i-1]) continue;
            int l = i+1, r = n-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 Solution

import java.util.*;
class Solution {
    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 (nums[i] > 0) break;
            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;
    }
}

Python Solution

def threeSum(nums):
    nums.sort()
    res = []
    for i, a in enumerate(nums):
        if a > 0: break
        if i > 0 and a == nums[i-1]: continue
        l, r = i+1, len(nums)-1
        while l < r:
            s = a + nums[l] + nums[r]
            if s == 0:
                res.append([a, 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

JavaScript Solution

function threeSum(nums) {
    nums.sort((a,b)=>a-b);
    const res = [];
    for (let i = 0; i < nums.length-2; i++) {
        if (nums[i] > 0) break;
        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;
}

Complexity: O(n²) time, O(1) extra space (excluding output)

Follow-ups: 3Sum Closest (return the triple closest to target), 4Sum (add one more fixed pointer), 3Sum with multiplicity (count triplets with repetition allowed).