In-Place Array Partition

Opening scenario

Sort Colors (LC 75). An array has only 0s, 1s, and 2s (red/white/blue). Sort it in place, one pass, O(1) extra space — you may not use a library sort or counting+rewrite if the interviewer bans the two-pass version. Follow-up: Wiggle Sort II (LC 324) — reorder so nums[0] < nums[1] > nums[2] < nums[3] .... The signs are strict, so no two adjacent values may be equal. For this follow-up, assume the input is nonempty and a valid wiggle arrangement exists.

LC numbers identify LeetCode problems.

For Sort Colors, keep track of which positions are already settled and which still need inspection. What must happen to those regions after each swap?

Question progression

Q1 — What does the easy two-pass solution give up?

Question: The simplest correct LC 75 solution counts 0s/1s/2s then overwrites. Why might the interviewer reject it, and what is the cost you're trying to beat?