3Sum and Sort Colors: Pair Search and Partitioning

Sorting can reveal the decisions hidden in an array

Sorting is not merely preparation for binary search. It creates an order that tells you how pointer movement changes a result. If a sum is too small, moving toward larger values increases it. If a sum is too large, moving toward smaller values decreases it.

That information has a price:

• sorting usually costs O(n log n);
• it changes the input unless a copy is made;
• original indices are lost unless values are paired with their indices.

For 3Sum, the answer asks for value combinations rather than original positions, so sorting is useful and allowed.

From three nested loops to one fixed value and two pointers

A direct 3Sum search chooses every possible triple:

choose first value
  choose second value
    choose third value

That is O(n³). Instead, sort the array and fix one value at index i. The remaining question becomes:

nums[left] + nums[right] = -nums[i]

This is the sorted two-sum problem from the first reading. For each fixed value, sweep the remaining suffix with two converging pointers in O(n) time. Repeating that for O(n) fixed positions gives O(n²) after sorting.

Worked trace

Start with:

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

After sorting:

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

Fix -4. The other two values would need to sum to 4, but the largest available pair is 1 + 2 = 3, so no triple exists for this fixed value.

Fix the first -1:

fixed = -1, left = -1, right = 2
sum = 0 → record [-1, -1, 2]

move inward to left = 0, right = 1
sum = 0 → record [-1, 0, 1]

The second -1 should not be fixed again; it would recreate the same combinations.

Duplicate control has two separate jobs

There are two sources of duplicate output:

1. The fixed value may equal the previously fixed value.
2. After finding a triple, the left or right pointer may move onto an equal value.

Skip a fixed value when nums[i] === nums[i - 1]. After recording a triple, move both pointers, then advance past repeated boundary values.

function threeSum(nums: number[]): number[][] {
  nums.sort((a, b) => a - b)
  const triples: number[][] = []

  for (let i = 0; i < nums.length - 2; i += 1) {
    if (i > 0 && nums[i] === nums[i - 1]) continue
    if (nums[i] > 0) break

    let left = i + 1
    let right = nums.length - 1

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right]

      if (sum < 0) {
        left += 1
      } else if (sum > 0) {
        right -= 1
      } else {
        triples.push([nums[i], nums[left], nums[right]])
        left += 1
        right -= 1

        while (left < right && nums[left] === nums[left - 1]) left += 1
        while (left < right && nums[right] === nums[right + 1]) right -= 1
      }
    }
  }

  return triples
}

The early break is safe because the array is sorted. Once the fixed value is positive, every later value is also positive, so three later values cannot sum to zero.

Correctness in plain language

For a fixed i, the pointers enclose every remaining pair that has not been eliminated. If the sum is too small, the current left value cannot work with any smaller right value, so advancing left is safe. If the sum is too large, the current right value cannot work with any larger left value, so decreasing right is safe. A match is recorded before both boundaries move.

The outer loop eventually fixes every distinct value that could begin a triple. Together, these facts cover all unique triples without testing every combination.

Sort Colors: Partition the Array With Three Pointers

“Two pointers” often means “a small number of indices that divide the input into regions.” Sort Colors uses three indices to arrange values 0, 1, and 2 in one pass without a general-purpose sort.

At the start of every iteration, maintain four regions:

[ zeros | ones | unknown values | twos ]
 0      low    current          high    end

More precisely:

• indices before low contain only 0;
• indices from low to current - 1 contain only 1;
• indices from current through high are not classified yet;
• indices after high contain only 2.

This is the Dutch National Flag invariant. The goal is to shrink the unknown region until nothing remains.

function sortColors(nums: number[]): void {
  let low = 0
  let current = 0
  let high = nums.length - 1

  while (current <= high) {
    if (nums[current] === 0) {
      ;[nums[low], nums[current]] = [nums[current], nums[low]]
      low += 1
      current += 1
    } else if (nums[current] === 1) {
      current += 1
    } else {
      ;[nums[current], nums[high]] = [nums[high], nums[current]]
      high -= 1
    }
  }
}

Why current does not move after swapping a 2

The value brought in from high came from the unknown region. It might be 0, 1, or 2, so it must still be examined. Only high moves because the outgoing 2 has reached its settled region.

When swapping a 0 with low, the incoming value at current is known to be 1 unless low === current. The region between low and current was already the ones region, so both indices can advance safely.

Trace: [2, 0, 2, 1, 1, 0]

current sees 2 → swap with high: [0,0,2,1,1,2], high moves
current sees 0 → swap with low:  [0,0,2,1,1,2], low and current move
current sees 0 → swap with low:  [0,0,2,1,1,2], low and current move
current sees 2 → swap with high: [0,0,1,1,2,2], high moves
current sees 1 → current moves
unknown region is empty

Complexity and decision guide

3Sum takes O(n²) time: O(n log n) sorting plus O(n) sweeps for O(n) fixed values. The output can itself contain O(n²) triples. Sort Colors takes O(n) time and O(1) auxiliary space.

Use sort–fix–sweep when fixing one value reduces a combination problem to a monotonic two-value search. Use region pointers when the input must be partitioned into a small, known set of categories. In both cases, name the settled and unsettled regions before writing the loop.