Nas | 3Sum

In one line

Fix one number at a time and hunt for a pair that cancels it out: which turns three unknowns into a Two Sum II problem run once per fixed value.

time O(n^2)space O(1)

Given an array, find every unique triplet that sums to zero. Checking every triple directly costs $O(n^3)$ . Even before that, "every unique triplet" hides a second problem: the same values can be found more than once unless duplicates are handled deliberately.

Sorting first solves both problems at once. It makes the two-pointer sweep valid, and it puts equal values next to each other so they're cheap to skip.

Why fixing one value turns this into Two Sum II

Reduce to a problem you've already solved

Fixing nums[i] as the pivot turns "three numbers sum to zero" into "two numbers sum to -nums[i]", exactly Two Sum II, just with a target that moves as the outer loop advances.
The sorted order that makes the inner two-pointer sweep valid is the same proof as before: the sum tells you which side is hopeless to keep.
Once nums[i] > 0, no pivot from here on can reach zero with two non-negative-or-larger partners, so the outer loop can stop.

What sorting doesn't solve by itself

Skipping duplicate values inside the inner sweep only avoids repeating a pair for one fixed pivot; you still need to separately skip a pivot value that repeats the previous one.
It doesn't bound the output size: in the worst case (many zeros) the result itself has $O(n^2)$ triplets, so the total work can't beat that no matter how the pointers move.
Sorting discards the original indices (fine here, since the answer only needs values, not positions).

Signals in the problem statement

"triplets" or "three numbers" that sum to a target
"no duplicate triplets in the result"
asked for every valid combination, not just one
values (not original positions) matter in the answer

The pattern

1Sort the array.
2
For each index i, skip it if it repeats the previous pivot.
3
Two-pointer the remainder for target -nums[i], skipping repeat values on left and right after recording a hit.
4Stop the outer loop once nums[i] > 0.

@itsnas three-sum.ts

codethree-sum.ts

function threeSum(nums: number[]): number[][] {
  nums.sort((a, b) => a - b)
  const result: number[][] = []
 
  for (let i = 0; i < nums.length - 2; i++) {
    if (nums[i] > 0) break
    if (i > 0 && nums[i] === nums[i - 1]) continue // skip pivot dupes
 
    let left = i + 1
    let right = nums.length - 1
 
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right]
      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]])
        while (left < right && nums[left] === nums[left + 1]) left++
        while (left < right && nums[right] === nums[right - 1]) right--
        left++
        right--
      } else if (sum < 0) {
        left++
      } else {
        right--
      }
    }
  }
 
  return result
}

main

Nas (@itsnas)

fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
    nums.sort();
    let mut result = Vec::new();
 
    for i in 0..nums.len().saturating_sub(2) {
        if nums[i] > 0 {
            break;
        }
        if i > 0 && nums[i] == nums[i - 1] {
            continue;
        }
 
        let (mut left, mut right) = (i + 1, nums.len() - 1);
 
        while left < right {
            let sum = nums[i] + nums[left] + nums[right];
            if sum == 0 {
                result.push(vec![nums[i], nums[left], nums[right]]);
                while left < right && nums[left] == nums[left + 1] {
                    left += 1;
                }
                while left < right && nums[right] == nums[right - 1] {
                    right -= 1;
                }
                left += 1;
                right -= 1;
            } else if sum < 0 {
                left += 1;
            } else {
                right -= 1;
            }
        }
    }
 
    result
}

main

Nas (@itsnas)

std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
  std::sort(nums.begin(), nums.end());
  std::vector<std::vector<int>> result;
 
  for (int i = 0; i < (int)nums.size() - 2; i++) {
    if (nums[i] > 0) break;
    if (i > 0 && nums[i] == nums[i - 1]) continue;
 
    int left = i + 1, right = nums.size() - 1;
 
    while (left < right) {
      int sum = nums[i] + nums[left] + nums[right];
      if (sum == 0) {
        result.push_back({nums[i], nums[left], nums[right]});
        while (left < right && nums[left] == nums[left + 1]) left++;
        while (left < right && nums[right] == nums[right - 1]) right--;
        left++;
        right--;
      } else if (sum < 0) left++;
      else right--;
    }
  }
 
  return result;
}

main

Nas (@itsnas)

func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	var result [][]int
 
	for i := 0; i < len(nums) - 2; i++ {
		if nums[i] > 0 {
			break
		}
		if i > 0 && nums[i] == nums[i-1] {
			continue // skip pivot dupes
		}
 
		left, right := i+1, len(nums) - 1
 
		for left < right {
			sum := nums[i] + nums[left] + nums[right]
			switch {
			case sum == 0:
				result = append(result, []int{nums[i], nums[left], nums[right]})
				for left < right && nums[left] == nums[left+1] {
					left++
				}
				for left < right && nums[right] == nums[right-1] {
					right--
				}
				left++
				right--
			case sum < 0:
				left++
			default:
				right--
			}
		}
	}
 
	return result
}

main

Nas (@itsnas)

def three_sum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []
 
    for i in range(len(nums) - 2):
        if nums[i] > 0:
            break
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # skip pivot dupes
 
        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]])
                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
            elif total < 0:
                left += 1
            else:
                right -= 1
 
    return result

main

Nas (@itsnas)

Complexity

Time

O (n^{2})

An O(n) two-pointer sweep runs once per pivot, dominating the O(n log n) sort.

Space

O (1)

Auxiliary space only, excludes the sort's internal use and the output list itself.

Common pitfalls

1
Forgetting to skip duplicate pivots
Not comparing nums[i] to nums[i - 1] reruns the identical inner sweep for equal pivot values, producing the same triplet more than once.
2
Forgetting to skip duplicates after a hit
Advancing left and right by one without first skipping past equal neighbours re-records the same triplet on the next iteration.
3
Starting the inner pointers at the wrong index
left and right must start at i + 1 and n - 1: starting left at 0 lets the pivot pair with itself.
4
Moving the wrong inner pointer
Same inversion risk as Two Sum II, just against a moving target: move left when the sum is too small, right when it's too big.

Variants worth knowing

1
3Sum Closest: track the closest sum seen instead of matching exactly.
2
4Sum: fix two pivots instead of one, then two-pointer the rest; the same idea nested a level deeper.
3
Valid Triangle Number: fixes the largest value instead of walking forward, and counts a whole range of pairs per step instead of one at a time.

Practice, easiest first

3SumMedium

3Sum ClosestMedium

4SumMedium

Valid Triangle NumberMedium

3Sum

Why fixing one value turns this into Two Sum II

The pattern

Complexity

Common pitfalls

Variants worth knowing

Practice, easiest first

What's next in the notebook?

Valid Triangle Number

Two Sum II

Container With Most Water

Two Pointers