Sort Colors

Difficulty: Medium

Problem

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red (0), white (1), and blue (2).

You must solve this problem without using the library's sort function. Can you do it in one pass?

Example

Input: nums = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]
Explanation: After sorting: all 0s (red) first, then all 1s (white), then all 2s (blue).

Brute-force approach

Count occurrences of each color, then overwrite the array.

Steps

  1. Count occurrences of 0s, 1s, and 2s
  2. Overwrite array: first count0 zeros
  3. Then count1 ones
  4. Then count2 twos

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

Trade-offs

  • Requires two passes through the array
  • Not a true one-pass algorithm
  • Can we do better with three pointers?

Optimal approach

Key insight: Maintain three regions: [0, low) contains 0s, [low, mid) contains 1s, (high, n-1] contains 2s. The unknown region is [mid, high].

Dutch National Flag: use three pointers to partition in one pass.

Steps

  1. Initialize low=0, mid=0, high=n-1
  2. While mid <= high:
  3. If nums[mid]=0: swap with low, increment both
  4. If nums[mid]=1: just increment mid
  5. If nums[mid]=2: swap with high, decrement high only

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