Arrange Three Encoded Colors without Library Sorting
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
The entries of `nums` encode three colors as 0, 1, and 2. Rearrange the supplied array in place so all 0s come first, followed by all 1s, then all 2s. Keep the count of each value unchanged. Using a library sorting function is forbidden.
```cpp
void sortColors(vector<int>& nums);
```
The displayed result is the changed argument; the function returns no array.
### Examples
```text
Input: nums = [1,2,0,1,0]
Array after call: [0,0,1,1,2]
```
```text
Input: nums = [2,2,0,0]
Array after call: [0,0,2,2]
```
### Constraints
- `1 <= nums.length <= 300`.
- Each value is 0, 1, or 2, representing red, white, or blue respectively.
- Mutate the array in place without calling a library sort.
### Source follow-up
Can you do this in one pass with constant extra space?
Overview: Rearrange a three-color array in place without library sorting, including a one-pass constant-space follow-up.
