Sort Three Categories In Place
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an array `items` containing only the values `0`, `1`, and `2`, where each value represents a category. Rearrange the array in-place so that all `0`s come first, followed by all `1`s, then all `2`s.
Requirements:
- Modify the input array in-place.
- Use `O(1)` extra space.
- Aim for a single-pass `O(n)` solution.
Example:
```text
Input: items = [2, 0, 2, 1, 1, 0]
Output: items = [0, 0, 1, 1, 2, 2]
```
Quick Answer: This question evaluates proficiency in in-place array manipulation, constant-space algorithms, and linear-time partitioning techniques. Commonly asked in Coding & Algorithms interviews to assess algorithmic efficiency, pointer/index management, and reasoning about invariants, it focuses on practical application of algorithmic concepts rather than purely theoretical understanding.
You are given an array `items` containing only the values `0`, `1`, and `2`, where each value represents a category. Rearrange the array in-place so that all `0`s come first, followed by all `1`s, then all `2`s.
You must modify the input array in-place, use `O(1)` extra space, and aim for a single-pass `O(n)` solution.
For testing, return the modified array after sorting.
Constraints
- 0 <= len(items) <= 10^5
- Each element in items is one of: 0, 1, 2
- The solution must use O(1) extra space
Examples
Input: ([2, 0, 2, 1, 1, 0],)
Expected Output: [0, 0, 1, 1, 2, 2]
Explanation: After rearranging in-place, all 0s come first, then 1s, then 2s.
Input: ([0],)
Expected Output: [0]
Explanation: A single-element array is already sorted.
Hints
- Try maintaining three regions in the array: one for `0`s, one for unknown values, and one for `2`s.
- When you see a `2`, swap it toward the end, but do not immediately move past the new value swapped into the current position.