LeetCode 3Sum: Sort + Two Pointers Step by Step

3Sum is LeetCode problem 15, 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.

Brute Force

Try every triple and collect unique results.

def three_sum(nums):
    result = set()
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    triplet = tuple(sorted((nums[i], nums[j], nums[k])))
                    result.add(triplet)
    return [list(t) for t in result]

Time: O(n^3). Space: O(k) for the result set. For n = 3000 this is around 2.7 * 10^10 operations, well beyond what LeetCode will accept.

Optimal Solution

Sort the array. Then for each fixed index i, run a two-pointer sweep on the suffix to find pairs that sum to -nums[i]. Skip duplicates carefully at every level.

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

Line by line:

• Sort so that we can both move pointers monotonically and skip duplicates by adjacency.
• If nums[i] > 0, the remaining numbers are all positive after sorting and cannot sum to zero. Break early.
• Skip i if it equals the previous i, otherwise we would produce the same triplet again.
• left and right sweep the suffix [i + 1, n - 1] looking for pairs summing to -nums[i].
• When we find a match, record it and advance both pointers past any duplicates.
• If the sum is too small, advance left. If too large, retreat right.

The duplicate-skipping after a match is the part people forget. Without it, inputs like [-2, 0, 0, 2, 2] produce [-2, 0, 2] twice.

Walk Through an 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]].

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

• LeetCode 1 Two Sum
• LeetCode 16 3Sum Closest
• LeetCode 18 4Sum
• LeetCode 259 3Sum Smaller
• LeetCode 454 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.