3Sum explained: how to solve it with sorting and two pointers

In this article

1. Before you start
2. Why interviewers ask this
3. 3Sum from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page belongs to the coding interview patterns guide. If you have not met sorting before a sweep, the merge intervals walkthrough uses the same habit.

Why interviewers ask this

3Sum is a short problem with a clear gap between a slow answer and a good one, so it shows whether a candidate can improve a first idea. Candidates report it in several forms: a "Three Sum" item reported by a Spotify candidate, a Java sort-and-two-pointers item reported by a ByteDance/TikTok candidate, and a request to return the total number of triples that sum to zero, reported by a Tekion candidate. These are candidate reports, not company statements.

A weak answer writes three nested loops and stops. A strong answer names that cost, sorts the array, and explains why each pointer move is safe. A Staff-level answer also handles repeated values without a set of triples, states the time and space cost, and says what changes when the target is not zero. The duplicates rule is where most correct-looking code fails, so it is worth practicing aloud.

3Sum from first principles

3Sum problem

The 3Sum problem is the task of finding every set of three numbers in an array that add to zero, where the same position is never used twice and each set of values is reported once. It is the three-number case of a family that asks for k numbers.

Two-pointer technique

The two-pointer technique is a way of searching a sorted array by keeping one index at each end of a range and moving whichever one the current comparison shows cannot be part of an answer, so the range shrinks without testing every pair.

In plain words

Imagine a row of price tags sorted from cheapest to dearest, and you must pick two that together hit an exact budget. Start with the cheapest and the dearest. If they cost too much, the dearest tag cannot work with anything left, so drop it. If they cost too little, the cheapest cannot work with anything left, so drop that one. You never look back. The analogy breaks in one place: 3Sum has three tags, so you first lock one in and run this search on the rest.

In one precise sentence, 3Sum fixes each number a in sorted order and asks whether two numbers to its right add up to minus a, which a pair of pointers answers in one pass.

Step 1: Sort the array

Sorting the array is what makes every later move justified. Input: the unsorted array. Output: the same values in increasing order, with equal values next to each other. For the example [-25, -10, -7, -3, 2, 4, 8, 10], which is the array used on the 3SUM page of Wikipedia, it is already sorted.

Sorting costs far less than the search that follows: for 1,000 numbers it is on the order of 9,966 comparisons, against 498,501 pointer steps at most.¹ Without sorting, you cannot say that the values beyond a pointer are all larger or all smaller, so you cannot discard anything. You now have an ordered array where "too big" always means "look further left".

Step 2: Fix one number and aim at its opposite

Fix the number at position i, called a, and look only at positions after i. If the three numbers add to zero, the other two must add to minus a. Input: a and the range to its right. Output: a pair-sum target. Put a left pointer just after a and a right pointer at the last position.

Only positions to the right of a are searched, because any triple that uses a smaller position was already covered when that smaller number was fixed. With a = -10 in the example the target for the pair is 10. The subarray sum equals k solution uses the complement-lookup idea from the hash method instead of pointers.

Step 3: Move the pointers by the sign of the sum

Add a, the left value and the right value. Input: the three values. Output: a decision. If the sum is below zero, the left value is too small for every remaining right value, so move the left pointer right. If the sum is above zero, move the right pointer left. If it is zero, you have a match.

Walking a = -10 through the example, the sums are -7, -3, 2 and then 0, so the pointers move three times before the match.¹ Because the pointers only move inward, a valid triple is never skipped; this is the correctness argument given for the algorithm on the Wikipedia page, and Baran, Demaine and Pătraşcu (2008) describe the same quadratic method. Each pointer move discards values permanently, which is why the pass is linear for each fixed number.

1 · Sort2 · Fix a3 · Move pointers4 · RecordReplay

Step-by-step description

1. Sorting makes each pointer move safe.
2. Aim the pointers at minus a.
3. The sign of the sum picks the pointer.
4. A zero sum is recorded.

• A sum below zero moves the left pointer right.
• A sum above zero moves the right pointer left.
• The triple -10, 2, 8 sums to zero.

Step 4: Record a match and skip repeated values

After a match, record the triple and move both pointers inward. A sum of zero records a triple, and with repeated values you must also skip them, or the same triplet appears twice. A triplet is a set of three values reported as one answer. Skip a left value equal to the one before it, and a right value equal to the one before it.

Also skip a when it equals the previous fixed number. On the common sample [-1, 0, 1, 2, -1, -4], sorted to [-4, -1, -1, 0, 1, 2], this yields two triples, [-1, -1, 2] and [-1, 0, 1], in seven pointer steps.¹ Without skipping, [-1, 0, 1] would be found twice. Confirm with the interviewer that each set of values is reported once.

Text description of the diagram

• A sum below zero moves the left pointer right.
• A sum above zero moves the right pointer left.

Here is the whole method as code.

def three_sum(nums):
    nums.sort()                      # sorting makes every pointer move safe
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue                 # skip a repeated fixed number
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1        # skip repeated left values
                right -= 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1       # skip repeated right values
            elif total > 0:
                right -= 1           # too large: move the right pointer left
            else:
                left += 1            # too small: move the left pointer right
    return result

The outer loop fixes a number and the inner loop is one inward pass, so the running time is O(n²) after an O(n log n) sort. Apart from the sort and the output list, the code keeps only a few index variables, so the extra space is O(1). The call nums.sort() changes the caller's list; copy it first if that matters.

Worked example

Take the sorted array -25, -10, -7, -3, 2, 4, 8, 10. Fix a = -25: the sums are -25, -22, -18, -13, -11 and -7, all below zero, so the left pointer climbs until it meets the right pointer and no triple starts with -25.¹ Fix a = -10: the sums are -7, -3, 2 and 0, which gives the triple (-10, 2, 8). Fix a = -7: the pair (-3, 10) gives the triple (-7, -3, 10). Fixing -3 and later values finds nothing, since no pair to their right adds to the needed amount. The whole array has 19 pointer steps in total and exactly two triples.¹

The step bound is (n minus 2) times (n minus 1) divided by 2: the first fixed number allows at most n minus 2 pointer steps, the next one fewer, and so on.¹ Growing the array tenfold multiplies this bound by roughly one hundred, which is what quadratic means. The brute-force count grows by roughly one thousand per tenfold, which is cubic.

Trade-offs and edge cases

Sort and two pointers is worst-case quadratic and needs no hashing, according to the 3SUM page of Wikipedia and Baran, Demaine and Pătraşcu (2008), who describe both quadratic algorithms. The same page describes a hash-table alternative that, in integer models of computing, solves the problem in quadratic time on average, not in the worst case. Beyond the sort itself, the pointer method keeps only a few index variables; the sort's own memory depends on the language and library.

Text description of the diagram

• Brute force checks every triple, which is cubic.
• Sort and two pointers is worst-case quadratic.
• The hash set method is quadratic on average.

Edge cases to test: fewer than three numbers (return an empty result); all zeros, where one triple (0, 0, 0) is correct and the skip rules must not hide it;¹ a fixed value a above zero, so the loop can stop early because all three numbers are positive (this early stop holds only for target zero); and the target. The target can be any constant, not only zero, as the Wikipedia page notes: compare the sum with that constant, not with zero. Sorting first is also the key move in merge intervals. A sliding window over two indices, a cousin of two pointers that needs no sorting, solves longest substring without repeating characters.

How to answer it in an interview

The spoken structure: name the slow answer, sort, fix one and aim two pointers at its opposite, explain the sign rule, then handle duplicates and say the cost.

Common mistakes

• "I'll use a set of triples to remove duplicates." (works but costly) That stores and hashes every triple. (right) "Sorting puts equal values together, so I skip repeated values with the pointers and need no set."
• "After a match I move one pointer." (wrong) With a and the left value fixed, only one right value works, so both pointers must move. Moving only one wastes a step, and with repeated values it reports the same triple again. (right) "I move both pointers inward and skip equal neighbors."
• "Two pointers works on any array." (wrong) The moves are justified only by order. (right) "I sort first; then too big means move the right pointer."
• "Hashing is always quadratic." (wrong) The hash approach is quadratic on average, in integer models. (right) "Sort and pointers gives the worst-case bound."
• "Quadratic is proven optimal." (wrong) The original conjecture that quadratic is optimal was refuted in 2014 by algorithms faster by a logarithmic factor; the open conjecture is that no O(n^(2−ε)) algorithm exists. (right) "Quadratic is the expected interview answer; the exact lower bound is still open."

Follow-up questions

Why do you sort the array before solving 3Sum?

Sorting lets you say that every value right of a pointer is at least as large and every value left of it at most as large, so one comparison discards a whole pointer position safely. It also puts duplicates side by side, so skipping them is one comparison.

How do you avoid duplicate triplets in 3Sum?

After sorting, skip a fixed number that equals the one before it. After a match, move each pointer past values equal to the one it just used. In the sample [-4, -1, -1, 0, 1, 2], the second -1 is never fixed, yet it still serves as the left pointer for the first.¹

How do you count the triples that sum to zero?

First ask whether to count distinct value sets or position triples. The same pass counts distinct sets with a counter at each match; for position triples, multiply the sizes of blocks of equal values and do not skip repeated fixed values. A Tekion candidate reported being asked for the total number of triples.

What changes if the target is not zero?

Only the comparison: you aim the pair at the target minus a. The Wikipedia page notes that any constant can replace zero.

How do you find the intersection of two integer arrays with two pointers?

Sort both arrays, then keep one pointer in each. Advance the pointer on the smaller value; when the two values are equal, record the value and advance both, skipping repeats if each value should appear once. The time is O(n log n + m log m) for the sorts plus one linear pass; a hash set of the shorter array gives the same answer in linear time on average. A related sorting-based selection problem is compared in K closest points to origin.

Can 3Sum be solved faster than quadratic time?

The original conjecture that the trivial quadratic algorithm is optimal was refuted in 2014 by Allan Grønlund and Seth Pettie, who gave a deterministic algorithm faster by a logarithmic factor (Grønlund and Pettie, 2014). The open conjecture is that no O(n^(2−ε)) algorithm exists for any ε above zero. The class of problems called 3SUM-hard was introduced by Gajentaan and Overmars in 1995, in the paper "On a class of O(n^2) problems in computational geometry" listed in the sources. For an interview, quadratic remains the expected answer.

Sources

1. 3SUM - Wikipedia — Wikipedia (live page, read 2026-10-26), 26 Oct 2026
2. Threesomes, Degenerates, and Love Triangles (arXiv 1404.0799) — arXiv (Grønlund and Pettie), 3 Apr 2014
3. On a class of O(n^2) problems in computational geometry — Computational Geometry (Gajentaan and Overmars), 1 Oct 1995
4. Subquadratic Algorithms for 3SUM — Algorithmica (Baran, Demaine and Pătraşcu), 1 Jan 2008