15% off all plans & roadmaps Use code

See plans

3Sum

Updated

TL;DR: Find every unique triplet in an array that sums to zero. Sort the array, fix one number, and close in on the other two with converging pointers. Skip repeated values so no triplet appears twice.

Problem

Given an integer array nums, return all triplets [nums[i], nums[j], nums[k]] where i, j, and k are all different indices and nums[i] + nums[j] + nums[k] == 0.

The answer must not contain the same triplet twice. The order of the triplets, and the order of the numbers inside a triplet, does not matter.

Example 1

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: (-1) + 0 + 1 = 0, 0 + 1 + (-1) = 0, and (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2].

Example 2

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum to 0.

Example 3

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums to 0.

Constraints

  • 3 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5

Constraints that matter

  • n up to 3000 rules out O(n^3) in the worst case: that is about 4.5 billion triples to check (n choose 3), far too many for a time limit.
  • n up to 3000 makes O(n^2) fine: about 9 million steps, which runs well within a second in every language.
  • Values fall within -10^5 to 10^5, so a sum of three values is at most 3 * 10^5 in size. No integer overflow is possible, even in Java or C#.
  • The answer must contain no duplicate triplets, and the input can hold many repeated values. You need a plan for uniqueness, not only for finding sums.
  • The order of the output does not matter, so you are free to sort the input first.

View on LeetCode

Hints

Hint 1

This is a two pointers problem hiding behind a three-number sum.

Hint 2

Try every group of three indices i < j < k and keep the ones that sum to zero.

Solution

Intuition

This is a two pointers problem hiding behind a three-number sum. If you fix one number a, you need two other numbers that add up to -a. That is Two Sum with a target, and Two Sum on a sorted array has a clean answer with a pointer at each end.

Picture a sorted row of price tags with one shopper at each end. If the total is too low, the left shopper steps to a bigger tag. If it is too high, the right shopper steps to a smaller one, so each step throws away a tag that cannot work.

Sorting makes the pointer moves safe. If the current sum is too small, only moving the left pointer right can raise it. If the sum is too big, only moving the right pointer left can lower it. Neither move can skip a valid pair.

Sorting also puts equal values next to each other. The problem asks for unique triplets, so you must avoid reusing the same value in the same role. After sorting, you compare a value with its neighbour and skip when they match. You need no set of triplets at all.

The cost is one sort, O(n log n), plus one pointer sweep per fixed number, O(n) each. The total is O(n^2), which is the best known bound for general 3Sum. Remember the pattern: sort, fix one, converge two.

Watch the pattern animation

Worked example

Input: nums = [-3, -2, -1, 0, 1, 2, 3]
Output: [[-3, 0, 3], [-3, 1, 2], [-2, -1, 3], [-2, 0, 2], [-1, 0, 1]]
Explanation: The array is already sorted and has no repeated values. Of the 35 possible triplets, exactly five sum to zero: -3+0+3, -3+1+2, -2+-1+3, -2+0+2 and -1+0+1. Every other choice of three values gives a positive or negative total.

Approach 1: Brute force with a set

Try every group of three indices i < j < k and keep the ones that sum to zero. To avoid duplicates, sort the array first so equal triplets look identical, then store each found triplet in a set. Only triplets not yet in the set go into the answer.

This is correct and needs no insight. It is also slow, because it examines every triple even when most of them can never work.

Steps

  1. Copy and sort the array so every triplet is written in ascending order.
  2. Loop i from 0 to n-1.
  3. Loop j from i + 1 to n-1.
  4. Loop k from j + 1 to n-1.
  5. If nums[i] + nums[j] + nums[k] == 0, build the triplet as a key.
  6. If the key is not in the seen set, add it to the set and to the result.
  7. Return the result.

Dry run

Sorted input: [-3,-2,-1,0,1,2,3], so n = 7 and there are 35 index triples.

  • (-3,-2,-1) sums to -6, skip. (-3,-2,0) sums to -5, skip. This continues for every triple that starts with -3.
  • (-3,0,3) sums to 0. It is new, so it goes into the result.
  • (-3,1,2) sums to 0. New, added.
  • Starting with -2: (-2,-1,3) and (-2,0,2) both sum to 0 and are added.
  • Starting with -1: (-1,0,1) sums to 0 and is added.
  • Every other triple has a nonzero sum.

All 35 triples were checked, and the result is [[-3,0,3],[-3,1,2],[-2,-1,3],[-2,0,2],[-1,0,1]].

Complexity

TimeO(n^3)
SpaceO(n)

Here n is the array length. The three nested loops visit n choose 3 triples, which grows as n^3 / 6, so time is O(n^3). The sorted copy takes O(n) space. The seen set holds at most one entry per distinct answer triplet, which can reach O(n^2) entries in the worst case. For n = 3000 the loops make around 4.5 billion checks, so the solution times out.

PythonTested in our runner

from typing import List, Optional

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        n = len(nums)
        seen = set()
        result = []
        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:
                        t = (nums[i], nums[j], nums[k])
                        if t not in seen:
                            seen.add(t)
                            result.append(list(t))
        return result

Approach 2: Sort, then hash map lookup

What's slow: the innermost loop re-scans the array to find a third number that the first two already determine. Given a and b, the third value must be -a - b. Searching for it linearly wastes O(n) work per pair.

The insight that fixes it: replace that scan with a hash map lookup. Sort the array, then store each value's last index in a map. For each pair (i, j), compute c = -a - b and check whether c appears at an index greater than j. Skipping repeated values for i and j keeps triplets unique without a set.

Steps

  1. Sort the array.
  2. Build a map from each value to its last index in the sorted array.
  3. Loop i from 0 to n-3, skipping it when nums[i] == nums[i-1].
  4. Loop j from i + 1 to n-2, skipping it when j > i + 1 and nums[j] == nums[j-1].
  5. Compute c = -nums[i] - nums[j].
  6. If the map has c with last index greater than j, record [nums[i], nums[j], c].
  7. Return the result.

Dry run

Sorted input: [-3,-2,-1,0,1,2,3]. The map sends each value to its index, for example -3 -> 0 and 3 -> 6.

  • i = 0 (a = -3): j = 1 gives c = 5, missing. j = 2 gives c = 4, missing. j = 3 (b = 0) gives c = 3 at index 6 > 3, so record [-3,0,3]. j = 4 (b = 1) gives c = 2 at index 5 > 4, so record [-3,1,2]. j = 5 gives c = 1 at index 4, not greater than 5. j = 6 is out of range for the inner loop.
  • i = 1 (a = -2): j = 2 (b = -1) gives c = 3, record [-2,-1,3]. j = 3 (b = 0) gives c = 2 at index 5 > 3, record [-2,0,2]. j = 4 gives c = 1 at index 4, not greater than 4. j = 5 gives c = 0 at index 3, rejected.
  • i = 2 (a = -1): j = 3 (b = 0) gives c = 1 at index 4 > 3, record [-1,0,1]. j = 4 gives c = 0 at index 3, rejected. j = 5 gives c = -1 at index 2, rejected.
  • i = 3 (a = 0): every c is negative or at a smaller index, so nothing is recorded. i = 4 finds nothing either.

The result is the five expected triplets.

Complexity

TimeO(n^2)
SpaceO(n)

Here n is the array length. Sorting costs O(n log n), building the map costs O(n), and the double loop runs at most n * n / 2 times with an O(1) average lookup each, so time is O(n^2). The map holds one entry per distinct value, so extra space is O(n), plus the sort. The last-index check guarantees the third number sits to the right of j, so the same element is never used twice.

PythonTested in our runner

from typing import List, Optional

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        n = len(nums)
        # value -> last index where it appears
        last = {v: i for i, v in enumerate(nums)}
        result = []
        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, n - 1):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                c = -nums[i] - nums[j]
                # the third value must sit to the right of j
                if last.get(c, -1) > j:
                    result.append([nums[i], nums[j], c])
        return result
Converging (Sorted Array Target Sum) pattern infographic for 3Sum

Solution pattern

Converging (Sorted Array Target Sum)

Part of Two Pointers

Approach 3: Sort, then converging two pointersOptimalConverging (Sorted Array Target Sum)

What's slow: the hash map approach still visits every pair (i, j) and pays for hashing and extra memory. For a fixed i, the sorted order already tells you which way to move, so you do not need to test every j.

The insight that fixes it: for each fixed i, put left at i + 1 and right at the end. If the sum is negative, increase left. If it is positive, decrease right. Each move discards a value that cannot be part of any answer with this i, so one sweep costs O(n) with no hashing. After a hit, skip equal neighbours to keep triplets unique.

Why it is correct. For a fixed i, every valid pair lies between left and right in the sorted array. If the sum is negative, nums[left] cannot reach zero with any value at or before right, since those values are no larger. The same argument removes right when the sum is positive, so the sweep finds every triplet for this i.

Steps

  1. Sort the array.
  2. Loop i from 0 to n-3. Stop early if nums[i] > 0, since all later values are positive too.
  3. Skip i when nums[i] == nums[i-1] so the same first value is not used twice.
  4. Set left = i + 1 and right = n - 1.
  5. While left < right, compute total = nums[i] + nums[left] + nums[right].
  6. If total < 0, move left right. If total > 0, move right left.
  7. If total == 0, record the triplet, then move left past all copies of its value and right past all copies of its value.
  8. Return the result.

Dry run

Sorted input: [-3,-2,-1,0,1,2,3]. Each row shows the state before the move.

inums[i]leftrightnums[left]nums[right]totalaction
0-316-23-2too small, left++
0-326-13-1too small, left++
0-336030record [-3,0,3], left=4, right=5
0-345120record [-3,1,2], left=5, right=4
1-226-130record [-2,-1,3], left=3, right=5
1-235020record [-2,0,2], left=4, right=4
2-136032too big, right--
2-135021too big, right--
2-134010record [-1,0,1], left=4, right=3
3046134too big, right--
3045123too big, right--
41-----nums[i] > 0, stop

The loop ends with [[-3,0,3],[-3,1,2],[-2,-1,3],[-2,0,2],[-1,0,1]].

Complexity

TimeO(n^2)
SpaceO(1)

Here n is the array length. Sorting costs O(n log n). For each of the n values of i, left and right together move at most n steps before they meet, so the sweep is O(n) and the total is O(n^2). Besides the sort and the output list, you store only a few integers. Extra space is O(1) if the sort is in place, or O(log n) for the sort stack in some languages.

PythonTested in our runner

from typing import List, Optional

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        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
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total < 0:
                    left += 1
                elif total > 0:
                    right -= 1
                else:
                    result.append([nums[i], nums[left], nums[right]])
                    # skip all copies of the values just used
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
        return result

Common mistakes

  • Skipping duplicates with if nums[i] == nums[i+1]: continue for the outer loop. This looks ahead and drops the first copy, so [-1,-1,2] is lost. Compare with the previous element, nums[i] == nums[i-1], and only when i > 0.
  • Not moving past duplicates after a match, so the same triplet is added again. After recording a triplet, advance left while nums[left] == nums[left+1] and retreat right while nums[right] == nums[right-1], then do one more left++ and right--.
  • Forgetting the bounds in the skip loops: while nums[left] == nums[left+1] without left < right. On input like [0,0,0] this can step past the end of the array. Always write while left < right and ....
  • Returning right after the first match for a given i. Several pairs can complete the same i, as in -3 with (0,3) and (1,2). After a hit, keep both pointers moving and continue the loop.
  • Skipping i using nums[i] == nums[i-1] without sorting first. Equal values are only adjacent in sorted order, so duplicates slip through. Sort the array before the loop.
  • Breaking out of the outer loop when nums[i] >= 0 instead of nums[i] > 0. That drops the [0,0,0] triplet. Break only when nums[i] is strictly positive.
  • Skipping duplicates with if j > 0 and nums[j] == nums[j-1] in the hash approach. That can compare nums[j] to nums[i] and drop a valid pair like [-1,-1,2]. Use j > i + 1 so the check only compares two second-position candidates.

Edge cases

  • [0,0,0] returns [[0,0,0]]. The break condition must allow nums[i] == 0.
  • [0,0,0,0] also returns [[0,0,0]], one triplet, not four. Duplicate skipping must handle long runs.
  • [1,2,3] has no zero-sum triplet and returns []. The early break on a positive first value covers this.
  • [-1,-1,2] returns [[-1,-1,2]]. The two -1 values are different indices, so reusing a value is allowed when it appears twice.
  • [-2,0,0,2,2] returns [[-2,0,2]] once, even though two zeros and two twos could form four index combinations.
  • All negative values, such as [-5,-4,-3], return []. Pointers close without a hit.
  • Maximum size with 3000 values: the O(n^2) approaches finish in well under a second, while brute force does not.

Follow-ups interviewers ask

Can you solve it without sorting?
Yes, with a hash set per fixed element. You then need another way to remove duplicates, such as storing sorted triplets in a set. That keeps O(n^2) time but needs extra memory for the set and more hashing, so sorting is usually the cleaner choice.
How would you generalize this to 4Sum or kSum?
Sort the array, then recurse. Fix one number and solve (k-1)Sum on the rest, until you reach Two Sum with two pointers. The time is O(n^(k-1)) for k >= 2, ignoring the sort. Duplicate skipping works the same way at every level.
What if you only need to count the triplets, or find the sum closest to zero?
The same sort and two pointers work. For closest, track the best absolute difference as the pointers move, and move the pointers by the sign of the current sum. Counting with duplicates needs care: when the pair values match, count combinations from run lengths instead of skipping.

3Sum FAQ

What is the time complexity of 3Sum?

The two pointers solution runs in O(n^2) time, where n is the array length. Sorting costs O(n log n), and each of the n fixed values triggers one O(n) pointer sweep. The brute force triple loop is O(n^3).

Why use two pointers for 3Sum?

After sorting, the sum of the two pointed values moves predictably. A small sum means only the left pointer can fix it, and a large sum means only the right pointer can. So each step safely discards one value, and one sweep finds every pair for the fixed number.

Can 3Sum be solved in O(1) extra space?

Almost. The two pointers version uses only a few integers beyond the sort and the output. An in-place sort such as heap sort gives true O(1) extra space, while most built-in sorts use O(log n) or O(n) space. The output list is not counted.

Why does 3Sum sort the array first?

Sorting enables both the pointer movement rule and the cheap duplicate check. Equal values land next to each other, so you compare with a neighbour instead of keeping a set of triplets. The O(n log n) sort is dominated by the O(n^2) sweep.

How do you avoid duplicate triplets in LeetCode 15?

Skip a fixed value if it equals the previous fixed value. After finding a triplet, move left forward past equal values and right backward past equal values. Every triplet then has a distinct first, second and third value combination.

Is a hash map solution for 3Sum as fast as two pointers?

Both are O(n^2) time. The hash map version uses O(n) extra space and pays hashing costs on each pair, so two pointers is usually faster in practice and uses less memory.

Asked at

See which companies ask this — Pro

Practise it