medium

Sort Colors

Sort an array of three distinct values in place in a single pass.

1. Define the problem

Sort Colors

Given an array nums with n objects colored red, white, or blue, represented by the integers 0, 1, and 2, sort them in place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. You must solve this problem without using the library's sort function. This uses the Dutch National Flag algorithm: three pointers , one extra beyond the usual two, but the same converging-boundary idea — low and high mark the boundaries of the 0s and 2s already placed, while mid scans forward through the unknown region.

Constraints

  • n == nums.length
  • 1 ≤ n ≤ 300
  • numsi is 0, 1, or 2.

Example

Inputnums = [2, 0, 2, 1, 1, 0]
Output[0, 0, 1, 1, 2, 2]

Explanation After sorting in place, all 0s come first, then all 1s, then all 2s.

2. Visualize the solution

Three pointers converge on the unsorted middle

Three pointers converge on the unsorted middle
Statusinit

low=0, mid=0, high=5. nums[mid]=2, so swap it with nums[high] and pull high inward.

What happens in this step

low = 0, mid = 0 (value 2), high = 5 (value 0)
nums[mid] = 2, so swap it with nums[high]

nums[0] and nums[5] trade places — high pulls inward from index 5 to index 4; mid stays at 0 since the swapped-in value is still unknown.
Step 1 of 6

Steps to visualize

  1. low marks the boundary just past the last placed 0; high marks the boundary just before the last placed 2; mid scans the unknown region between them.
  2. If numsmid is 0, swap it with numslow, then advance both low and mid.
  3. If numsmid is 1, it is already in place, so just advance mid.
  4. If numsmid is 2, swap it with numshigh and pull high inward — but do not advance mid, since the swapped-in value is still unknown.
  5. Stop when mid passes high; every element has been placed.
3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Three pointers converge on the unsorted middle
Statusinit

low=0, mid=0, high=5. nums[mid]=2, so swap it with nums[high] and pull high inward.

What happens in this step

low = 0, mid = 0 (value 2), high = 5 (value 0)
nums[mid] = 2, so swap it with nums[high]

nums[0] and nums[5] trade places — high pulls inward from index 5 to index 4; mid stays at 0 since the swapped-in value is still unknown.
Step 1 of 6
4. Solution

Solution

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

  while (mid <= high) {
    if (nums[mid] === 0) {
      const temp = nums[low];
      nums[low] = nums[mid];
      nums[mid] = temp;
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      const temp = nums[mid];
      nums[mid] = nums[high];
      nums[high] = temp;
      high--;
    }
  }

  return nums;
}
Time
O(n)
Space
O(1)
5. Test cases

Test cases

InputExpectedCovers
nums = [2, 0, 2, 1, 1, 0][0, 0, 1, 1, 2, 2]example from the docstring
nums = [0, 1, 2][0, 1, 2]already-sorted input is left unchanged
nums = [1, 1, 1][1, 1, 1]every element the same color
nums = [2, 1, 0][0, 1, 2]fully reverse-sorted input
nums = [1, 0, 2, 1, 0, 2, 0][0, 0, 0, 1, 1, 2, 2]colors interleaved with an uneven count of each

Keep reading