3Sum

+10

You get a list of integers nums. Find every triplet [a, b, c] of values taken from three different positions of nums with a + b + c = 0. Write each triplet in non-decreasing order (a ≤ b ≤ c) and list each distinct triplet once, even when several choices of positions produce it. Return the triplets sorted by their first value, then by their second.

Function

threeSum(nums: integer-array) → integer-2d-array

numsinteger-array: the list of integers, with at least three elements
Returnsinteger-2d-array: every distinct triplet that adds up to 0, each in non-decreasing order, the list sorted

Constraints

3 ≤ nums.length ≤ 3000
-10⁵ ≤ nums[i] ≤ 10⁵
At least one triplet adds up to 0.
Two triplets are the same when they hold the same three values.

Examples

Input: nums = [-2, 0, 1, 1, -1, 2]
Output: [[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]
Explanation: Three triplets make 0. [-2, 1, 1] uses the value 1 twice because 1 sits at two positions; [-1, 0, 1] can use either 1 but appears once.

Input: nums = [0, 0, 0, 0]
Output: [[0, 0, 0]]
Explanation: Any three of the four zeros add up to 0. That is four choices of positions, but they all give the same triplet, so the answer holds [0, 0, 0] once.

Follow-up

The same pattern solves 4Sum: fix two values and run two pointers on the rest. Can you write it in O(n³) and keep the duplicate rules right at every level?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Checking every triple costs O(n³), and each triplet must appear once even when values repeat. Sorting fixes both: equal values sit side by side, so you skip repeats by comparing neighbours, and with the smallest value fixed the other two form a pair-sum problem on a sorted list.

Try every triple

Correct, but does not finish on the largest tests

Intuition

Sort the list, then try every three positions i < j < k. The values come out in order, so a triplet is written correctly the moment you find it, and the nested loops miss nothing. Each loop skips a position whose value equals the one that same loop tried before it, so every distinct triplet appears once. [-2, 1, 1] still uses both ones, because the skip compares only inside one loop.

There are about n³/6 triples: n = 3000 means 4.5 × 10^9 sums.

Algorithm

Sort nums.
Loop i, then j from i+1, then k from j+1. In each loop, skip a position whose value equals the one that loop tried before it.
Record [nums[i], nums[j], nums[k]] when the three add up to 0, and return the triplets in the order found.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 1):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # same second value as the round before
            for k in range(j + 1, n):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                if nums[i] + nums[j] + nums[k] == 0:
                    triplets.append([nums[i], nums[j], nums[k]])
    return triplets

Fix one value, find the pair with a hash set

Intuition

With nums[i] fixed you need two later values that add up to -nums[i]: Two Sum. Walk j to the right of i with a set of the values passed. If need = -nums[i] - nums[j] is in the set, [nums[i], need, nums[j]] adds up to 0. One i costs O(n) on average, the search O(n²).

After a match, move j past the copies of nums[j]: with the first and third values fixed, the middle one is fixed too. need comes from an earlier sorted position, so the triplet is in order, but as j moves right need shrinks: one i yields [-2, 1, 1] before [-2, 0, 2]. Reverse each group before you add it.

Algorithm

Sort nums.
For each i, stop when nums[i] > 0 and skip i when nums[i] equals nums[i-1].
Start an empty set. For each j from i+1, compute need = -nums[i] - nums[j]. If need is in the set, record [nums[i], need, nums[j]] and move j past the copies of nums[j].
Add nums[j] to the set and go on to the next j.
Reverse the triplets found for this i and append them to the answer.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        group = []
        seen = set()  # values between position i and position j
        j = i + 1
        while j < n:
            need = -nums[i] - nums[j]
            if need in seen:
                group.append([nums[i], need, nums[j]])
                while j + 1 < n and nums[j + 1] == nums[j]:
                    j += 1
            seen.add(nums[j])
            j += 1
        # need shrinks as nums[j] grows, so this group came out backwards
        group.reverse()
        triplets.extend(group)
    return triplets

Sort and use two pointers

Intuition

Fix nums[i], put lo at i+1 and hi at the last index. If the sum is below 0, nums[lo] falls short even with the largest value left, nums[hi], so it cannot pair with anything still in range: move lo right. Above 0 is the mirror case: nums[hi] is too large even with the smallest value left, so move hi left. Each step drops one value for good without losing a triplet, so one i costs at most n steps and the search O(n²), with no extra memory.

Repeats need two rules. Skip an i whose value equals the one before it. After a match, step lo past copies of its value. hi needs no rule: a copy of the old nums[hi] now gives a sum above 0 and moves away by itself. Since i visits distinct values in increasing order and lo only moves right, the triplets come out sorted.

Algorithm

Sort nums.
For each i, stop when nums[i] > 0 and skip i when nums[i] equals nums[i-1].
Set lo = i+1 and hi = n-1. While lo < hi, add up nums[i], nums[lo] and nums[hi].
Below 0, move lo right. Above 0, move hi left.
At 0, record the triplet, move both pointers, then move lo past copies of the value it used.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        lo, hi = i + 1, n - 1
        while lo < hi:
            total = nums[i] + nums[lo] + nums[hi]
            if total < 0:
                lo += 1
            elif total > 0:
                hi -= 1
            else:
                triplets.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
    return triplets

Pitfalls and edge cases

Skipping i when nums[i] equals nums[i+1]. In [-1, -1, 2] that loses [-1, -1, 2]; compare with nums[i-1].
Stopping when nums[i] ≥ 0 instead of nums[i] > 0. That misses [0, 0, 0].
Removing repeats at the end. On 3000 zeros the loop records millions of copies of [0, 0, 0] before any cleanup.
Using one position twice. A hash-set version that fills the set with the whole list up front turns [-2, 1, 3] into [-2, 1, 1].
Forgetting to reverse each group in the hash-set version. The triplets must come out sorted.

Frequently asked questions3

What is the time complexity of 3Sum?

The sort-and-two-pointers solution runs in O(n²) time: sorting costs O(n log n), and each of the n choices of the first value takes one O(n) sweep. It needs O(1) extra space apart from the sort and the output. Checking every triple takes O(n³).

Should I use two pointers or a hash set for 3Sum?

Both run in O(n²) time. Two pointers need no extra memory and hand you the triplets already in order. A hash set costs O(n) memory and needs care to keep positions distinct and the output sorted. The hash-set idea matters when you cannot sort, as in Two Sum where you return the original indices.

Can 3Sum be solved faster than O(n²)?

Not by much. The best known algorithms beat n² only by a few logarithmic factors, and many hardness results in computational geometry assume that no algorithm reaches a power of n below 2. O(n²) is the answer interviews expect.

def threeSum(nums):
    # Write code here

Test #1

Test #2

Argument

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

Expected Output

[[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]

3Sum

Function

Constraints

Examples

Hints

Solution

Try every triple

Fix one value, find the pair with a hash set

Sort and use two pointers

Pitfalls and edge cases

Frequently asked questions3

Similar problems