How do you sort an array containing only 0s, 1s, and 2s?
This problem tests your knowledge of the Dutch National Flag algorithm. It evaluates your ability to sort in-place with minimal passes.
Why Interviewers Ask This
It checks if you can implement specialized sorting algorithms rather than relying on built-in sorts. Interviewers value the O(n) time and O(1) space solution demonstrated here.
How to Answer This Question
Explain the three-pointer technique: one for current, one for next 0, and one for next 2. Walk through swapping logic when encountering 0s or 2s. Emphasize that 1s are left in the middle automatically. Provide a trace of the array state during execution.
Key Points to Cover
- Use three-pointer technique
- Sort in single pass
- Minimize swaps
- Achieve O(n) time
Sample Answer
I use three pointers: low, mid, and high. Mid iterates through the array. If we find a 0, we swap with low and increment both. If 2, we swap with high and decrement high. 1s stay put. This single pass sorts the array in…
Common Mistakes to Avoid
- Using standard sort functions
- Creating extra arrays
- Incorrect pointer updates
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.