3Sum — Sort and Two Pointers, Step by Step

3Sum is rated Medium. It is the natural follow-up to Two Sum and it is the problem people most often botch in interviews because they forget to handle duplicate triplets. The pattern, sort then two-pointer scan, is worth memorizing.

The Problem

Given an integer array nums, return all unique triplets [a, b, c] such that a + b + c == 0. The triplets in the result must not be duplicates.

Example:

Input:  nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]

The order of triplets in the output does not matter, but each triplet itself must be unique as a multiset.

Intuition

The brute force is to try every triple and collect unique results in a set of sorted tuples. That is O(n^3) time which, for n up to a few thousand, is well beyond what an online judge will accept.

The key idea: if we sort the array first, then for each fixed index i we can run a two-pointer sweep on the suffix to find pairs that sum to -nums[i]. Sorting gives us two benefits at once. First, monotone movement lets us discard halves of the search space. Second, duplicates become adjacent so dedup is a simple “skip while equal to the previous” check.

The duplicate-skipping is the part people forget. Without it, inputs like [-2, 0, 0, 2, 2] produce [-2, 0, 2] twice. We need three layers of skipping: on the outer fixed index, and on both pointers after a match.

Explanation with Example

nums = [-1, 0, 1, 2, -1, -4]. After sorting: [-4, -1, -1, 0, 1, 2].

• i = 0, nums[i] = -4. target = 4. left = 1, right = 5. Sums: -1 + 2 = 1, -1 + 2 = 1, 0 + 2 = 2, 1 + 2 = 3. None reach 4. No matches.
• i = 1, nums[i] = -1. target = 1. left = 2, right = 5. Sum = -1 + 2 = 1. Match. Add [-1, -1, 2]. Advance both. left = 3, right = 4. Sum = 0 + 1 = 1. Match. Add [-1, 0, 1]. left = 4, right = 3. Loop ends.
• i = 2, nums[i] = -1. Same as previous. Skip.
• i = 3, nums[i] = 0. target = 0. left = 4, right = 5. Sum = 1 + 2 = 3. Too big. right = 4. Loop ends.

Return [[-1, -1, 2], [-1, 0, 1]].

sorted:  [ -4 , -1 , -1 ,  0 ,  1 ,  2 ]
idx:        0    1    2    3    4    5

i = 1  (fix -1)   target = -nums[i] = 1

         L                       R
[ -4 , -1 , -1 ,  0 ,  1 ,  2 ]
          ^                  ^
      nums[L] + nums[R] = -1 + 2 = 1   match -> [-1,-1,2]

                L         R
[ -4 , -1 , -1 ,  0 ,  1 ,  2 ]
                ^    ^
      nums[L] + nums[R] = 0 + 1 = 1    match -> [-1, 0,1]

                     L  R
                     ^<-^   L >= R, stop

outer i:   skip if nums[i] == nums[i-1]
inner L:   after match, skip nums[L] == nums[L-1]
inner R:   after match, skip nums[R] == nums[R+1]

same triplet appears at most once in the output

Code

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

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right) {
                int s = nums[left] + nums[right];
                if (s == target) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (s < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }
}

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> result;
        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 left = i + 1, right = n - 1, target = -nums[i];
            while (left < right) {
                int s = nums[left] + nums[right];
                if (s == target) {
                    result.push_back({nums[i], nums[left], nums[right]});
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (s < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }
};

Edge Cases

• Fewer than three elements. Return an empty list. The outer loop handles this naturally.
• All zeros like [0, 0, 0, 0]. The output is [[0, 0, 0]] exactly once, courtesy of the dedup checks.
• All positives or all negatives. No valid triplet exists. The early break helps in the all-positive case.
• Duplicates clustered together. The nums[left] == nums[left - 1] and nums[right] == nums[right + 1] checks are what keep the output unique.
• Already sorted input. No special path; sorting is idempotent.

Complexity Analysis

• Time: O(n^2). Sorting is O(n log n) and the nested two-pointer sweep is O(n^2).
• Space: O(1) extra ignoring the output, or O(log n) for the sort’s stack. The result list itself can hold up to O(n^2) triplets in the worst case.

How to Explain It in an Interview

• Restate the problem and confirm uniqueness is required.
• Mention the O(n^3) brute force and immediately move on.
• State the plan: sort, fix one element, two-pointer the rest.
• Explain why sorting helps: monotone movement lets us reject halves of the search space, and duplicates become adjacent so dedup is cheap.
• Code it. Talk through the dedup checks explicitly; this is where interviewers grade.
• Quote O(n^2) time and stop.

Related Problems

• Two Sum
• 3Sum Closest
• 4Sum
• 3Sum Smaller
• 4Sum II

The general two-pointer skeleton lives in two pointers technique. For the duplicate-handling intuition, hash maps from hashing and hash maps are an alternative tool.

Wrap up

3Sum is the test that you can write loop logic that is correct on duplicates without resorting to set-of-tuples patches. Once you can write the canonical sort plus two pointers from muscle memory, the entire kSum family becomes mechanical, including kSum reductions where you recursively peel off one fixed element at a time.