Two Pointers Rearranging in place
161. Sort Colors
You are given an array nums in which every element is 0, 1 or 2. Rearrange it so that all the 0s come
first, then all the 1s, then all the 2s.
Change nums itself. The function returns nothing; the answer is what nums holds after it finishes. The
array keeps its length, and each value appears as many times as it did before.
Aim for a single pass over the array with only O(1) extra memory.
Example 1
Input: nums = [2, 0, 1, 2, 1, 0, 0]
[0,0,0,1,1,2,2]Explanation: The array holds three 0s, two 1s and two 2s. Afterwards the three 0s sit at the front, the two 2s at the back, and the two 1s between them.
Example 2
Input: nums = [2, 2, 0, 2, 0]
[0,0,2,2,2]Explanation: There are no 1s, so the three 2s follow straight after the two 0s.
Example 3
Input: nums = [1]
[1]Explanation: A single element is already in order, so nothing moves.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105nums[i]is0,1or2
Clarifying questions
What you would ask an interviewer before writing any code.