Loading section...
Partitioning: Dutch National Flag
Concepts: pyDutchNationalFlag, pyThreeWayPartition
The Dutch National Flag problem (LeetCode 75: Sort Colors) uses THREE pointers to partition an array into three zones in a single pass. Given an array with values 0, 1, and 2, sort it in-place without using a sorting algorithm. The trick: maintain three pointers. A 'low' pointer tracks where the next 0 should go. A 'high' pointer tracks where the next 2 should go. A 'mid' pointer scans through the array. When mid finds a 0, swap with low and advance both. When mid finds a 2, swap with high and retreat high (but do not advance mid, because the swapped-in value has not been examined yet). When mid finds a 1, just advance mid. The subtle detail that candidates miss: when you swap mid with high, you do NOT advance mid. The value that was at position high has been swapped to position mid, and y