How do you sort an array containing only 0s, 1s, and 2s efficiently?
This problem, known as the Dutch National Flag problem, tests in-place sorting algorithms and two/three-pointer techniques. It is a favorite for assessing coding efficiency.
Why Interviewers Ask This
Interviewers ask this to see if candidates can achieve O(n) time complexity with O(1) space complexity. It checks their ability to manipulate pointers correctly and handle edge cases in a single pass. Standard sorting algorithms like QuickSort are less efficient here due to higher overhead.
How to Answer This Question
Explain the limitations of standard sorting algorithms which take O(n log n). Introduce the three-way partitioning approach using three pointers: low, mid, and high. Describe the logic: move 0s to the beginning, 2s to the end, and leave 1s in the middle. Provide a step-by-step walkthrough of the pointer movements and swapping logic.
Key Points to Cover
- Three-pointer technique for partitioning
- Single pass O(n) time complexity
- In-place sorting with O(1) space
- Handling boundaries correctly
Sample Answer
I would use the Dutch National Flag algorithm which sorts the array in a single pass. I maintain three pointers: one for the boundary of 0s, one for the current element being processed, and one for the boundary of 2s. As I iterate, if I encounter a 0, I swap it with the element at the low pointer and increment both. If I see a 2, I swap it with the high pointer and decrement high. 1s are left alone. This ensures O(n) time and O(1) space complexity.
Common Mistakes to Avoid
- Using built-in sort functions instead of custom logic
- Incorrectly updating pointers during swaps
- Failing to handle the case where mid crosses high
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 Object-Oriented Programming in Java and why is it important?
Easy
GoogleConvert Binary Tree to Doubly Linked List in Place
Hard
MicrosoftExplain the concept of graph components in data structures?
Medium
Microsoft