Home › 3Sum

3Sum

⚡ Difficulty: Medium 🏷️ Pattern: Sorting + Two Pointers 🏢 Asked at: PhonePe, Amazon, Google, Meta

Problem

Given an integer array nums, return all unique triplets [a, b, c] such that a + b + c == 0. No duplicate triplets in the output.

Example:

nums = [-1, 0, 1, 2, -1, -4]  →  [[-1, -1, 2], [-1, 0, 1]]

Approach

Reduce 3Sum to 2Sum

Sort the array. Fix one element nums[i], then the problem becomes: find two numbers in the rest that sum to -nums[i]. Because the array is sorted, use two pointers converging from both ends — O(n) per fixed element.

Skipping duplicates is the tricky part

Sorting groups equal values together, so:

Skip a fixed i if nums[i] == nums[i-1] (already handled).
After finding a valid triplet, advance left/right past equal values.

Early exit

Once nums[i] > 0, no triplet can sum to zero (all remaining values are positive) — break.

Complexity

	Time	Space
Sort + two pointers	O(n²)	O(1) extra (or O(n) for sort)
Brute force	O(n³)	O(1)

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;   // skip dup pivot
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++; right--;
            } else if (sum < 0) left++;
            else right--;
        }
    }
    return res;
}

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

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

Try It Yourself

Write your solution and run it live in C++, Java, Python, Go, Rust, and more — right here in the browser.

▶ Try it live

stdin

Output

Run your code to see output here.

Key Insight

Sorting unlocks two things at once: two pointers (turning the inner 2Sum into O(n)) and duplicate skipping (equal values sit next to each other). The “fix one, two-pointer the rest” pattern generalizes to 4Sum and kSum.

Follow-ups

4Sum → Fix two elements, two-pointer the rest → O(n³).
3Sum Closest → Track the sum nearest to target instead of exactly zero.
Count triplets < target → For each fixed i, all pairs between the pointers count in bulk.

Drop a comment below if you want the generalized kSum template 👇