AlgoMaster Logo

3Sum

mediumFrequency8 min readUpdated June 23, 2026

Understanding the Problem

We need to find all unique triplets (three elements) in the array that add up to zero. Two requirements make this harder than Two Sum.

First, we need all valid triplets, not just one. Second, we need to avoid duplicate triplets in our result. For example, if the array has two -1s, both [-1, 0, 1] using the first -1 and [-1, 0, 1] using the second -1 count as the same triplet. We only want it once.

Fixing one element nums[i] reduces the rest of the problem to a familiar one: the other two elements must sum to -nums[i], which is Two Sum. So 3Sum amounts to running a Two Sum search once per element.

Key Constraints:

  • 3 <= nums.length <= 3000 → With n up to 3000, O(n^2) gives us about 9 million operations, which is fine. O(n^3) gives 27 billion, which is too slow.
  • -10^5 <= nums[i] <= 10^5 → Values fit in a standard integer. No overflow concerns for sums of three elements.

Approach 1: Brute Force

Intuition

Check every combination of three indices (i, j, k) with i < j < k and test whether nums[i] + nums[j] + nums[k] == 0. Each match is a candidate triplet.

Duplicates still need handling, because the same three values can come from different index combinations. Sorting each found triplet before inserting it into a set normalizes the order: [-1, 0, 1] and [0, -1, 1] both become [-1, 0, 1], and the set keeps one copy.

Algorithm

  1. Initialize an empty set to store unique triplets.
  2. Use three nested loops to iterate over all combinations of indices (i, j, k) where i < j < k.
  3. For each combination, check if nums[i] + nums[j] + nums[k] == 0.
  4. If the sum is zero, sort the triplet and add it to the set.
  5. Convert the set to a list and return.

Example Walkthrough

1Try i=0, j=1, k=2: (-1)+0+1 = 0. Found [-1,0,1]
0
i
-1
1
0
j
2
1
k
3
2
4
-1
5
-4
1/7

Code

At n = 3000, the triple loop performs about 27 billion operations, well past any time limit. The next approach applies the reduction from the problem analysis: fix one element and solve the remaining pair search as Two Sum with a hash set.

Approach 2: Hash Set

Intuition

Fixing nums[i] turns the remaining search into Two Sum: find two elements after index i that sum to -nums[i]. With a hash set, each such search takes O(n). For each j past i, compute complement = -nums[i] - nums[j]; if the complement is among the values already scanned, the pair (complement, nums[j]) completes a triplet.

Duplicate handling relies on sorting the array first. Sorting puts equal values next to each other, which makes them cheap to skip: the outer loop skips repeated values of nums[i], and after recording a triplet the inner loop advances j past every remaining copy of nums[j].

This skipping catches every duplicate. For a fixed nums[i], take a valid pair of values (a, b) with a <= b. While j sits on an occurrence of a, the needed complement is b, which is at least as large and therefore has not appeared yet in the sorted scan. The pair is first recorded when j reaches an occurrence of b with a already in the set. All copies of b form one consecutive run, and the skip loop moves j past that entire run, so the same pair cannot be recorded a second time.

Algorithm

  1. Sort the array.
  2. For each index i from 0 to n-3:
    • Skip if nums[i] is the same as nums[i-1] (avoid duplicate first elements).
    • Set target = -nums[i].
    • Use a hash set to find pairs in nums[i+1...n-1] that sum to target.
    • For each nums[j], compute complement = target - nums[j].
    • If the complement is in the set, add [nums[i], complement, nums[j]] (already in sorted order, since the complement appeared earlier in the scan), then skip duplicates for j.
    • Otherwise, add nums[j] to the set.
  3. Return the result.

Example Walkthrough

1i=0, nums[i]=-4, target=4. Scan with hash set
0
-4
i
1
-1
2
-1
3
0
4
1
5
2
1/9

Code

This reaches O(n^2) time, but each outer iteration builds a hash set of up to n elements. The array is already sorted for duplicate handling, and sorted order supports a pair search that needs no extra memory at all: two pointers moving toward each other.

Approach 3: Sorting + Two Pointers (Optimal)

Intuition

The array is sorted anyway for duplicate handling, and after fixing nums[i], the goal is two elements in the remaining sorted subarray that sum to -nums[i]. In sorted data, a pair with a given sum can be found with two pointers and no extra memory.

Place one pointer left at the start of the remaining subarray (i+1) and another pointer right at the end. If the sum of the three elements is too small, move left right to increase it. If it's too large, move right left to decrease it. If it's exactly zero, we found a triplet.

Each pointer moves in only one direction, so the inner search is O(n). Combined with the outer loop, the total is O(n^2) with O(1) extra space.

Algorithm

  1. Sort the array.
  2. For each index i from 0 to n-3:
    • If nums[i] > 0, break (since the array is sorted, no three positive numbers can sum to zero).
    • Skip if nums[i] equals nums[i-1] (avoid duplicate first elements).
    • Set left = i + 1 and right = n - 1.
    • While left < right:
      • Compute sum = nums[i] + nums[left] + nums[right].
      • If sum < 0, increment left (need a larger value).
      • If sum > 0, decrement right (need a smaller value).
      • If sum == 0, add the triplet, then skip duplicates for both left and right.
  3. Return the result.

Example Walkthrough

1i=0, nums[i]=-4. left=1, right=5
0
-4
i
1
L
-1
2
-1
3
0
4
1
5
2
R
1/9

Code