thesarfo

Reference

Sort an Array of 0s, 1s, and 2s

The Dutch National Flag problem — sorting a three-valued array in a single pass with three pointers.

views 0

The Dutch National Flag problem. [2,0,1,2,0,1,0,2] → [0,0,0,1,1,2,2,2]. (LeetCode 75)

Brute force: run any general sort — O(n log n), unnecessary given only 3 distinct values.

Better — counting: count zeros, ones, and twos in one pass, then overwrite the array with that many 0s, then 1s, then 2s.

Optimal — Dutch National Flag algorithm, three pointers: low marks the boundary between 0s and 1s, mid is the element currently being processed, high marks the boundary between 1s and 2s.

  • arr[mid] == 0: swap with arr[low], advance both low and mid (the 0 is now placed).
  • arr[mid] == 1: already in the right zone, just advance mid.
  • arr[mid] == 2: swap with arr[high], decrement high — but don’t advance mid, since the newly-swapped-in element at mid hasn’t been checked yet.

Continue until mid passes high. Time: O(n), single pass. Space: O(1), sorted in place.