Sorting/Practice/Sort Colors (Dutch National Flag)

Sort Colors - Dutch National Flag Explained Visually

mediumTime: O(n)Space: O(1)

Keep three regions with three pointers: everything before low is 0, everything after high is 2, and the middle is unexplored. When the cursor sees a 0, swap it back to low; a 2, swap it forward to high; a 1, just move on.

Why it works

The invariants do all the work: the zero region and two region only grow, and the cursor never revisits a settled element. One pass, O(n) time, O(1) space - and crucially no second pass, which a two-pointer count-then-rewrite solution would need.

The problem

Given an array with values 0, 1, and 2 (representing red, white, blue), sort them in-place in a single pass without using Python's built-in sort.

Hints

  • Maintain three pointers: low (boundary of 0s), mid (current), high (boundary of 2s).
  • If nums[mid] == 0: swap with nums[low], advance both.
  • If nums[mid] == 1: just advance mid.
  • If nums[mid] == 2: swap with nums[high], decrement high (don't advance mid).

Test cases

InputExpected
sort_colors([2,0,2,1,1,0])[0,0,1,1,2,2]
sort_colors([2,0,1])[0,1,2]

Reference starter code

def sort_colors(nums):
    # Dutch National Flag algorithm
    # Three pointers: low, mid, high
    pass

nums1 = [2, 0, 2, 1, 1, 0]
sort_colors(nums1)
print(nums1)  # [0, 0, 1, 1, 2, 2]

nums2 = [2, 0, 1]
sort_colors(nums2)
print(nums2)  # [0, 1, 2]

Try it yourself

Solve it in the browser editor with real test cases and instant feedback - free, no signup needed.

Studying Sorting but not ready to grind? Get the 30-day plan by email.
One email with the study plan. No spam, unsubscribe anytime.