3Sum and Sort Colors: Pair Search and Partitioning

Sorting can reveal the decisions hidden in an array

The first reading used two pointers to find a pair with a target sum. We will build on that idea to find triples. Before adding a third value, recall the pair problem: choose two numbers at different indices whose sum equals a given target.

Sorting helps because it makes the effect of moving each pointer predictable. Place left at the smallest value and right at the largest. The “sum” we compare with the target is the sum of those two selected values—not the whole array.

The lesson is not simply “move toward larger or smaller numbers.” Sorted order lets us prove that an endpoint has no useful partner left. With duplicates, a move may leave the sum unchanged, but it still removes a candidate safely. Without sorted order, moving inward would not reliably change the sum in the intended direction.

Knowing that values increase from left to right helps us decide which pointer to move. But getting that order has three tradeoffs.

Sorting takes work

For the comparison sorting commonly used in these problems, we budget O(n log n) time. If sorting is followed by an O(n) two-pointer scan, the total is:

sorting + scan = O(n log n) + O(n) = O(n log n)

The scan is linear, but the entire solution is not. Sorting dominates the growth in work as the input gets larger.

Sorting can change the original array

JavaScript’s .sort() rearranges the array itself:

const nums = [8, 2, 5]
nums.sort((a, b) => a - b)

// nums is now [2, 5, 8]

If you need to preserve the original order, sort a copy instead:

const nums = [8, 2, 5]
const sorted = [...nums].sort((a, b) => a - b)

// nums is still [8, 2, 5]
// sorted is [2, 5, 8]

That copy costs O(n) extra space, in addition to any workspace used by the sorting implementation.

Sorted positions are not original positions

Consider the same values before and after sorting:

Before sorting:           After sorting:
index:  0  1  2           index:  0  1  2
value:  8  2  5           value:  2  5  8

For target 10, we find 2 + 8. Their sorted indices are 0 and 2, but their original indices were 1 and 0. Returning the sorted positions would answer a different question.

If the problem asks for original indices, keep that information attached before sorting:

const nums = [8, 2, 5]
const pairs = nums.map((value, index) => ({ value, index }))
pairs.sort((a, b) => a.value - b.value)

// [
//   { value: 2, index: 1 },
//   { value: 5, index: 2 },
//   { value: 8, index: 0 }
// ]

Sorting moves each whole pair, so every value still carries its original position. This also costs O(n) extra space. A plain sorted copy preserves the original array, but does not itself attach original indices to the sorted values.

Extend the pair search to three values

Now extend the goal: 3Sum asks for unique combinations of three values at distinct indices that add up to zero. For example, [-2, -1, 3] is a valid triple because -2 + -1 + 3 = 0. The answer asks for value combinations rather than original positions, so sorting is useful and allowed. The next step is to turn this triple search into the pair search we just traced.

From three nested loops to one fixed value and two pointers

We can already find two values with a target sum. Adding a third value seems to give us one more choice to try for every pair. The straightforward approach really does that: choose three different positions and test their total.

choose first value
  choose second value
    choose third value

That is O(n³). But suppose we temporarily choose -2 as the first value. What must the other two values add up to? They must total 2, because -2 + 2 = 0. We have turned this one part of 3Sum into a pair search with a known target.

To use that observation, sort the array and fix one value at index i: keep it unchanged while the other two pointers search. Rearranging the required total gives:

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

Search only the positions after i, starting at left = i + 1 and the last index for right. This prevents reusing the fixed element. It also gives every combination one index order: first i, then left, then right. We do not need to search the same three positions again in another order. Reset both search pointers when i advances.

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

Goal: Return every unique triplet of values that adds up to zero, using three different indices. We are returning values, not their positions.

What to follow: Fix the first value at index i, then search for the other two with left = i + 1 and right = nums.length - 1. “Left” means the left end of the remaining search range—not the element to the left of i. The indices always satisfy i < left < right while we test a triple.

Start with:

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

After sorting:

index:  0   1   2   3   4   5
value: -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. This summarizes the outcome; the basic algorithm still moves the pointers through that search range.

Fix the first -1:

i = 1, left = 2, right = 5          ← indices
nums[i] + nums[left] + nums[right]
   -1   +     -1     +      2       = 0 → record [-1, -1, 2]

move both pointers inward:
i = 1, left = 3, right = 4          ← indices
   -1   +      0     +      1       = 0 → record [-1, 0, 1]

move both inward again: left = 4, right = 3
the pointers cross → this fixed value's search is finished

Skip fixing the second -1 at index 2: its remaining range would only reproduce [-1, 0, 1]. Fixing 0 next cannot work because the remaining values, 1 and 2, make the sum positive. Later indices leave fewer than two partners.

The final answer is [[-1, -1, 2], [-1, 0, 1]]. The two -1 values in the first triplet are allowed because they come from separate indices.

Duplicate control has two separate jobs

Suppose we have found [-1, 0, 1] and added it to the answer. The array may contain another -1, so continuing the search could produce that same triplet again. Using different indices does not make it a new answer: 3Sum asks for unique value combinations. At the same time, [-1, -1, 2] is a legitimate answer if two separate -1s exist. We must avoid repeated answers without banning repeated values inside an answer.

How can we keep searching without recording the same combination twice? Consider the two moments when repetition can happen.

First, the outer loop may choose a fixed value that we have already fully searched. In [-1, -1, 0, 1], fixing the first -1 finds [-1, 0, 1]. Fixing the next -1 would find it again. The first search had access to every later partner available to the second search, so repeating it cannot produce a new value combination. Skip a fixed index when i > 0 and nums[i] === nums[i - 1].

Second, repetition can happen while the fixed index stays the same. In [-2, 0, 0, 2, 2], fixing -2 and choosing the outer 0 and 2 finds [-2, 0, 2]. Moving both pointers inward lands on another 0 and another 2. Those are new positions, but they would recreate the same answer. After recording the match, move both pointers and continue past values equal to the partners just used.

Why move both after a match? With the fixed value unchanged, keeping the same left value requires the same right value to reach zero, and vice versa. Another occurrence would only duplicate the answer. To find a new value combination, both partners must change. The code below applies these two rules at their respective levels.

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

The trace shows that this works for one input. But could the pointer moves or duplicate skips silently miss an answer elsewhere? To check that, follow an imagined valid triple through the search: its first index will be considered, and its remaining pair must either be found or be ruled out for a sound reason.

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

So far, pointers have helped us search for pairs and triples. We will now use moving boundaries for a different job: rearranging values into groups. The connection is the invariant—knowing what each processed region contains—not the target-sum logic.

Sort Colors gives an array containing only 0, 1, and 2, representing three colors. Arrange it in place with all zeroes first, then ones, then twos. For example, [2, 0, 1, 2, 0] must become [0, 0, 1, 2, 2].

A straightforward solution counts each value, then overwrites the array in that order. That takes two passes and constant extra space. Can we classify the values in one pass instead? We can send zeroes to the left, twos to the right, and leave ones between them. This is partitioning: dividing the array into regions with known contents.

Unlike the earlier pair search, this method uses three indices: low marks where the next zero belongs, current examines the next unknown value, and high marks where the next two belongs. Initially, the whole array is unknown.

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.

Now inspect nums[current]. A 0 belongs at the next left slot, so swap it with nums[low] and grow the zero region. A 1 is already where the middle region can grow, so advance current. A 2 belongs at the next right slot: swap it with nums[high] and shrink high. There is one important difference between those swaps: the value arriving from the right has not yet been examined. Keep current still until that replacement value has been classified too.

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

Suppose the array starts [2, 1, 0]. Swapping the first 2 with the last 0 gives [0, 1, 2]. The 2 has reached its final region, but the 0 that arrived at index 0 still needs to be counted as part of the zero region. What if we simply moved past it? Our boundaries would no longer describe the contents we claim they describe.

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]

We want [0, 0, 1, 1, 2, 2] without creating another array. Start with low = 0, current = 0, and high = 5. Follow which unknown value is examined and which boundary changes; a swap can leave the array looking unchanged while still settling a position.

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

We have used moving boundaries for two different tasks. Before choosing either method in another problem, separate the work they do. In 3Sum, fixing a new value restarts the pair search. In Sort Colors, the unknown region only gets smaller; no pass restarts.

That makes 3Sum O(n²) time: O(n log n) sorting plus an O(n) scan for each of O(n) fixed positions. Its pointer variables use constant space, but sorting may need extra workspace, and the returned answer can contain O(n²) triplets. Making a copy before sorting would add O(n) space. Sort Colors takes O(n) time and O(1) auxiliary space: each iteration classifies one value and shrinks the unknown region by one.

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.