Partitions an array into three regions — less than, equal to, and greater than a pivot — in one pass with three pointers. The classic problem of sorting an array of 0s, 1s, and 2s.
Partitions an array into three regions — less than, equal to, and greater than a pivot — in one pass with three pointers. The classic problem of sorting an array of 0s, 1s, and 2s.
Time complexity: O(n). Space complexity: O(1).
Core idea — Three pointers (low, mid, high) carve the array into a smaller-than region on the left, an equal region in the middle, and a greater-than region on the right.
What each pass accomplishes — Each step inspects the value at mid: smaller values swap left and both low and mid advance; larger values swap to the right and high retreats (mid stays to re-check the value that came back); equal values just advance mid. One pass fully partitions the array.
Use the interactive visualizer above to run Dutch National Flag (3-Way Partition) on your own input and watch every comparison, swap, and operation animate step by step — pause, scrub, or replay at any speed.