3Sum

Input: [-1, 0, 1, 2, -1, -4]. Answer: [-1, -1, 2] and [-1, 0, 1], each exactly once. Checking every triple is $O(n^3)$ .

Fix one, and it's Two Sum II

Sort first. Then pick a pivot nums[i], and the question "which three numbers sum to zero?" becomes "which two numbers, to the right of the pivot, sum to -nums[i]?" That's Two Sum II: two pointers closing in, one comparison deciding which side to drop.

Index 0: -4
Index 1: -1 (i)
Index 2: -1 (L)
Index 3: 0
Index 4: 1
Index 5: 2 (R)

Pivot -1, so L and R hunt for a pair summing to 1. -1 + 2 = 1: the first triplet, [-1, -1, 2].

After a hit, both pointers move in, and the sweep finds 0 + 1 = 1: the second triplet, [-1, 0, 1]. Running one $O(n)$ sweep per pivot gives $O(n^2)$ overall, and the sort's $O(n \log n)$ disappears inside that.

Where duplicates come from

Now the outer loop moves to the next pivot, index 2. It's another -1.

Index 0: -4
Index 1: -1 (done)
Index 2: -1 (i: skip)
Index 3: 0
Index 4: 1
Index 5: 2

Same pivot value as the last round. Its sweep can only find pairs the last round already found: [-1, 0, 1] again.

A pivot with the same value as the previous one hunts for the same target in a subset of the same numbers, so anything it finds is a repeat. Sorting put equal values side by side, which makes the fix one line: if nums[i] === nums[i - 1], skip it.

The same thing happens inside the sweep. After recording a hit, if the next L is the same value as the last one, it pairs with the same R partner and records the same triplet. So after each hit, step both pointers past equal neighbours before continuing.

Rule	Without it
Skip a pivot equal to the previous pivot	the whole sweep repeats its triplets
After a hit, skip equal neighbours of L and R	the same triplet twice in one sweep
Start L at `i + 1`, not 0	the pivot pairs with itself
Stop once `nums[i] > 0`	wasted sweeps: three positives can't sum to 0

Two skips and a sweep

@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)

$O(n^2)$ time, $O(1)$ extra space beyond the sort and the output. You can't do better than $O(n^2)$ in the worst case anyway: an input full of zeros and pairs can have $O(n^2)$ distinct triplets to return.

The shape generalises. 4Sum fixes two pivots and runs the same sweep inside; 3Sum Closest tracks the best difference instead of matching exactly. Valid Triangle Number flips it around and fixes the largest value, so that one comparison can count a whole range of pairs at once.

3SumMedium

3Sum ClosestMedium

4SumMedium

Valid Triangle NumberMedium

Fix one, and it's Two Sum II

Where duplicates come from

Two skips and a sweep

The Two Egg Drop Problem: Why the Answer Is 14

Invert This Binary Tree (For a CRUD Job)

Valid Triangle Number

Two Sum II