1 / 1
05A/191
Sort Colors
Problem Statement

Given an array nums containing only 0, 1, and 2, sort it in-place so that same colors are adjacent. Do not use the library sort for the intended interview solution. This is the Dutch National Flag problem.

Examples

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

Output: [0,0,1,1,2,2]

Explanation: All 0s move left, 1s stay in the middle, and 2s move right.

Input: nums = [2,0,1]

Output: [0,1,2]

Explanation: A single linear scan is enough with three pointers.

Custom Notes
  • low marks the next place for 0.
  • mid scans the unknown region.
  • high marks the next place for 2.
  • When swapping with high, do not increment mid yet.
  • Memory hook: left 0s, middle 1s, right 2s.
Brute Force Approach : TC: SC:
1 / 3

Algorithm: Use built-in sort or any comparison sort.

Pseudo:

  • Call sort(nums.begin(), nums.end()) or equivalent.

Time: O(n log n)

Space: Depends on sort implementation

Why mention it: It is correct but ignores the structure of the problem where values are only 0, 1, and 2.

Better Approach : TC: SC:
2 / 3

Algorithm: Count the number of 0s, 1s, and 2s, then overwrite the array.

Pseudo:

  • First pass: count zeros, ones, twos.
  • Second pass: fill the array with that many 0s, then 1s, then 2s.

Time: O(n)

Space: O(1)

Interview line: Easy and valid, but not the most elegant one-pass in-place partitioning answer.

Optimal Approach : TC: SC:
3 / 3

Algorithm: Maintain three pointers low, mid, and high.

Pseudo:

  • If nums[mid] == 0, swap nums[low] and nums[mid], then low++ and mid++.
  • If nums[mid] == 1, just mid++.
  • If nums[mid] == 2, swap nums[mid] and nums[high], then high-- only.
  • Continue while mid <= high.

Time: O(n)

Space: O(1)

Key insight: After swapping with high, the incoming value at mid is still unprocessed, so mid must stay.

PCode
1 / 3
sort nums using any standard comparison sort
RETURN nums
PCode
2 / 3
zeros = 0
ones = 0
twos = 0

FOR each value in nums
    increment zeros or ones or twos

rewrite nums with zeros copies of 0
then ones copies of 1
then twos copies of 2

RETURN nums
PCode
3 / 3
low = 0
mid = 0
high = n - 1

WHILE mid <= high
    IF nums[mid] == 0
        swap nums[low] and nums[mid]
        low = low + 1
        mid = mid + 1
    ELSE IF nums[mid] == 1
        mid = mid + 1
    ELSE
        swap nums[mid] and nums[high]
        high = high - 1

RETURN nums