Goal: All 0s on left, all 1s on right. Use two pointers!
Left Pointer: 0
Right Pointer: 0
Current Action
arr[left]=? arr[right]=?
📚 0-1 Sort (Dutch National Flag Variant)
Partition an array of 0s and 1s in linear time:
- Left pointer starts at 0, Right pointer at end
- Move left while arr[left] = 0
- Move right while arr[right] = 1
- When left < right and arr[left] = 1 and arr[right] = 0, swap!
- Time: O(n) | Space: O(1)