How would you sort an array of 0s, 1s, and 2s in linear time?
Direct Answer
This is a variation of the Dutch National Flag problem. It tests sorting efficiency and in-place manipulation skills.
Why Interviewers Ask This
Standard sorting algorithms take O(n log n), but this question challenges candidates to achieve O(n). Interviewers want to see if you know the three-pointer technique and can implement it without extra space. It evaluates your attention to detail in boundary conditions and loop invariants.
How to Answer This Question
Use three pointers: low, mid, and high. Initialize low and mid at the start, and high at the end. Iterate while mid is less than or equal to high. If the element at mid is 0, swap with low and increment both. If it is 1, just increment mid. If it is 2, swap with high and decrement high. Ensure you explain why this works and that it sorts in a single pass.
Key Points to Cover
- Three-pointer technique
- In-place swapping
- Single pass O(n) complexity
- Handling distinct values
Sample Answer
To sort this array in O(n) time, I would use the Dutch National Flag algorithm with three pointers. Low points to the end of the 0s section, mid scans the array, and high points to the start of the 2s section. When arr[m…
Common Mistakes to Avoid
- Using standard sort libraries
- Incorrect pointer movement logic
- Failing to handle the middle element correctly
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.