Sort Colors

Difficulty: Medium

You're given an array that contains only the values 0, 1, and 2 (think of them as three colors — say, red, white, and blue). Rearrange the array in place so that all the 0s come first, then all the 1s, then all the 2s.

Try to do this without calling a general-purpose sort function, and ideally in a single pass through the array.

Examples

Input: nums = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]

Input: nums = [2, 0, 1]
Output: [0, 1, 2]

Input: nums = [0]
Output: [0]

A single element is already sorted; there's nothing to rearrange.

Constraints

1 <= nums.length <= 300
nums[i] is 0, 1, or 2.

Approach

Since there are only three distinct values, sorting the array with a general-purpose comparison sort works, but it's more machinery than the problem actually needs and doesn't take advantage of there being just three possible values.

The optimal approach (often called the Dutch National Flag algorithm) uses three pointers: one tracking the next place a 0 should go (growing from the front), one tracking the next place a 2 should go (growing from the back), and one that scans through the array from left to right. Whenever the scanning pointer sees a 0, it swaps it toward the front; whenever it sees a 2, it swaps it toward the back; 1s are left where the scan finds them, since they belong in the middle. This sorts the whole array in a single pass, in place.

Solutions

Brute Force — Built-in Sort

Just hand the array to a general-purpose comparison sort. It's correct and simple, but it doesn't take advantage of the fact that there are only three possible values.

function sortColors(nums) {
  nums.sort((a, b) => a - b);
}

Time: O(n log n) · Space: O(log n) (typical sort implementation's internal stack space)

Optimal — Dutch National Flag (Three Pointers)

Keep three pointers: low marks the next spot for a 0, high marks the next spot for a 2 (from the back), and mid scans through the array. Swap 0s toward low and 2s toward high; when a 1 is seen, just move past it.

function sortColors(nums) {
  let low = 0;
  let mid = 0;
  let high = nums.length - 1;

  while (mid <= high) {
    if (nums[mid] === 0) {
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
      // mid isn't advanced here — the value swapped in from the back
      // still needs to be checked
    }
  }
}

Time: O(n) · Space: O(1)