How do you sort an array of 0s, 1s, and 2s in linear time?
Direct Answer
This problem asks for an efficient sorting strategy for an array containing only three distinct values. It tests the Dutch National Flag algorithm and in-place sorting skills.
Why Interviewers Ask This
Standard sorting takes O(N log N), but this specific case allows for O(N). Interviewers ask this to see if you recognize the limited range of values and can apply counting sort or the Dutch National Flag partitioning logic. It demonstrates attention to detail and optimization capabilities.
How to Answer This Question
Propose the Dutch National Flag algorithm using three pointers: low, mid, and high. Initialize low and mid at the start, high at the end. Iterate with mid: swap 0s to the low section, 2s to the high section, and move past 1s. Explain that this sorts the array in a single pass without extra space.
Key Points to Cover
- Three-pointer technique
- In-place swapping
- Single pass iteration
- Linear time complexity
Sample Answer
To sort an array of 0s, 1s, and 2s in linear time, I would use the Dutch National Flag algorithm. I'll maintain three pointers: low, mid, and high. As I iterate with mid, if I encounter a 0, I swap it with the element at…
Common Mistakes to Avoid
- Using standard sort functions
- Allocating extra space for counting
- Incorrect pointer updates
- Failing to handle boundary conditions
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.