How do you sort an array of 0s, 1s, and 2s in linear time?
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 low and increment both low and mid. If I find a 2, I swap it with the element at high and decrement high. If the element is 1, I simply increment mid. This ensures all 0s are moved to the front, 2s to the back, and 1s remain in the middle, completing the sort in O(N) time.
Common Mistakes to Avoid
- Using standard sort functions
- Allocating extra space for counting
- Incorrect pointer updates
- Failing to handle boundary conditions
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.
Related Interview Questions
How do you add two numbers represented by linked lists?
Medium
AmazonWrite Selenium and Java code to automate an Amazon search
Medium
InfosysHow do you implement binary search on a sorted array?
Easy
MicrosoftWhat is the difference between value type and reference type?
Easy
TCSConvert Binary Tree to Doubly Linked List in Place
Hard
MicrosoftDiscuss ACID vs. BASE properties
Easy
Microsoft