3Sum: Sorting Plus Two Pointers

LeetCode 3Sum is one of the most frequently asked medium problems in coding interviews. It builds directly on the two-pointer technique, but adds a layer that trips people up: duplicate handling. Once you see how the pieces fit together, the solution is clean and mechanical. Let's break it down.

The problem

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

The result must not contain duplicate triplets.

Example: nums = [-1, 0, 1, 2, -1, -4]. The answer is [[-1, -1, 2], [-1, 0, 1]].

Two things make this harder than Two Sum. First, you need all valid triplets, not just one pair. Second, you need to avoid returning the same triplet twice. The array has two -1 values, but [-1, -1, 2] should only appear once in the output.

Why brute force fails

The most naive approach: three nested loops, checking every possible triplet.

def three_sum_brute(nums):
    n = len(nums)
    result = set()
    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:
                    result.add(tuple(sorted([nums[i], nums[j], nums[k]])))
    return [list(t) for t in result]

This is O(n^3) time. For an array of 3,000 elements, that is 27 billion operations. Way too slow. And using a set of sorted tuples to handle duplicates is clunky. There is a much better way.

The sorting insight

Here is the key idea: sort the array first. Sorting costs O(n log n), which is cheap compared to the O(n^2) we will need anyway. But it buys us two huge advantages:

1. We can use two converging pointers (like Two Sum II on a sorted array) to find pairs that sum to a target in O(n) time.
2. We can skip duplicate values by simply checking if the current element is the same as the previous one.

After sorting [-1, 0, 1, 2, -1, -4], we get [-4, -1, -1, 0, 1, 2].

The strategy: fix one element at index i, then use two pointers (lo and hi) to find pairs in the remaining subarray that sum to -nums[i]. This reduces the three-sum problem to a series of two-sum problems on a sorted array.

Visual walkthrough

Let's trace through the algorithm on [-4, -1, -1, 0, 1, 2]. The purple pointer is i (fixed), orange is lo, and green is hi.

Notice how after finding [-1, -1, 2], both lo and hi move inward. And when i advances from index 1 to index 2, it skips because nums[2] == nums[1] (both are -1). That skip is what prevents duplicate triplets in the output.

The code

Here is the complete Python three sum solution:

def three_sum(nums):
    nums.sort()
    result = []
    n = len(nums)

    for i in range(n - 2):
        # Skip duplicate values for i
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        # Early termination: if smallest possible sum is positive, stop
        if nums[i] > 0:
            break

        lo, hi = i + 1, n - 1
        target = -nums[i]

        while lo < hi:
            s = nums[lo] + nums[hi]
            if s < target:
                lo += 1
            elif s > target:
                hi -= 1
            else:
                result.append([nums[i], nums[lo], nums[hi]])
                # Skip duplicates for lo and hi
                while lo < hi and nums[lo] == nums[lo + 1]:
                    lo += 1
                while lo < hi and nums[hi] == nums[hi - 1]:
                    hi -= 1
                lo += 1
                hi -= 1

    return result

Let's walk through the important parts:

• nums.sort() sorts the array in-place. This is what makes the two-pointer approach and duplicate skipping possible.
• if i > 0 and nums[i] == nums[i - 1]: continue skips duplicate values for the outer loop. If we already processed -1 as the fixed element, we do not process it again.
• if nums[i] > 0: break is an early exit. If the smallest remaining number is positive, no three positive numbers can sum to zero.
• target = -nums[i] converts the three-sum problem into a two-sum problem: find two numbers in the remaining subarray that add up to target.
• The inner while loops after finding a match skip over duplicate values for both lo and hi before moving the pointers inward.

How duplicate skipping works

Duplicates are the trickiest part of 3Sum. There are two places where they need to be handled, and both rely on the array being sorted.

Outer loop: skipping duplicate i values

When the outer loop advances, we check if nums[i] == nums[i - 1]. If so, we skip. Why? Because we already found every valid triplet that starts with that value. Running the inner two-pointer loop again with the same fixed element would produce the exact same results.

For our example, nums[1] and nums[2] are both -1. After processing i = 1, we found [-1, -1, 2] and [-1, 0, 1]. If we process i = 2 (also -1), we would find the same triplets again. So we skip.

Inner loop: skipping duplicate lo and hi values

After finding a valid triplet, both pointers need to skip past any duplicate values. Consider an array like [-2, 0, 0, 2, 2]. With i = 0 (value -2), target = 2. When lo points to the first 0 and hi points to the last 2, we find [-2, 0, 2]. If we just move lo right by one, we land on another 0 and find the same triplet. The while loops skip past all consecutive duplicates.

Complexity analysis

Time: O(n^2). Sorting is O(n log n). The outer loop runs n times, and for each iteration the two-pointer scan is O(n). Total: O(n log n) + O(n^2) = O(n^2).

Space: O(1) extra (ignoring the output array and the space used by the sort). The two-pointer scan uses only a few variables. Some sorting algorithms use O(log n) stack space, but no auxiliary data structures are needed.

You cannot do better than O(n^2) for 3Sum in the general case. There is a well-known theoretical lower bound. So this is optimal.

The building blocks

The 3Sum solution combines two fundamental building blocks that show up across many LeetCode problems:

Opposite-end convergence

The inner loop is a textbook opposite-end convergence pattern. Two pointers start at the ends of a sorted subarray and move inward. If the sum is too small, move the left pointer right. If too large, move the right pointer left. This narrows the search space by one element each step, and you never need to backtrack.

This same pattern powers:

• Two Sum II (sorted input, find one pair)
• Container With Most Water (maximize area between two lines)
• Trapping Rain Water (process the smaller side first)

If you have drilled opposite-end convergence on simpler problems, the inner loop of 3Sum will feel natural.

Skip-duplicates-sorted

The duplicate skipping technique is specific to sorted arrays. The idea: after processing a value, advance the pointer past all identical consecutive values. This guarantees each unique value is processed exactly once.

This same technique shows up in:

• Remove Duplicates from Sorted Array (skip in-place)
• 4Sum (same idea, one more nesting level)
• 3Sum Closest (skip to avoid redundant comparisons)

Once you recognize that sorting enables O(1) duplicate detection (just compare adjacent elements), this brick becomes second nature.

Edge cases to watch for

A few things that trip people up:

• All zeros. [0, 0, 0] should return [[0, 0, 0]]. The duplicate skip logic handles this correctly because it only skips when i > 0.
• No valid triplets. [1, 2, 3] has no triplet summing to zero. The early termination (nums[i] > 0) catches this immediately after sorting.
• Large arrays with many duplicates. Arrays like [-1, -1, -1, 0, 0, 0, 1, 1, 1] are stress tests for the duplicate handling. The skip logic keeps the output clean without a dedup set.
• Negative-only or positive-only arrays. If every element has the same sign (and is not zero), no valid triplet exists. The sorting and early termination handle this.

Problems that use the same bricks

Once you have opposite-end convergence and sorted duplicate skipping down, try these:

• Two Sum II: the core inner loop of 3Sum, in isolation
• 4Sum: add one more outer loop and one more layer of duplicate skipping
• 3Sum Closest: same structure, but track the closest sum instead of matching zero
• Container With Most Water: opposite-end convergence with a different objective
• Trapping Rain Water: opposite-end convergence with running maximums

You will not remember the duplicate logic

The 3Sum algorithm is not conceptually hard. Sort, fix one element, run two pointers. But the duplicate skipping has just enough fiddly details that you will forget exactly where the checks go. Should you check nums[i] == nums[i - 1] or nums[i] == nums[i + 1]? Do you skip before or after recording the triplet? Do you need the lo += 1; hi -= 1 after the skip loops?

These are the kinds of details that slip away after a week or two. And in an interview, getting the duplicate logic wrong means your solution produces wrong answers. That is worse than not solving it at all.

The fix is the same as always: drill the building blocks individually, then practice assembling them. Opposite-end convergence is a small, self-contained skill. So is skip-duplicates-sorted. Once both are automatic, the full 3Sum solution follows mechanically. You are not memorizing 25 lines of code. You are combining two bricks you already know.

Related posts

• The Two Pointers Pattern - The foundation of the inner loop, with converging pointer examples
• Trapping Rain Water - Another problem built on opposite-end convergence
• Two Sum - The simpler cousin that introduces complement lookup

---

Visual Learner? See how sorting algorithms work with our Quick Sort Visualization — the first step in the 3Sum solution.