mediumTwo pointersSorting target 25 min
Sort three colors
Every item of the list nums is 0, 1 or 2 (picture three paint colors: red, white and blue). Rearrange nums in place so that all the 0s come first, then all the 1s, then all the 2s.
Do not call sort or sorted, and do not build a second list: use only a few extra variables. The function returns nothing. The tests call it and then look at nums. A single pass over the list is possible.
Example 1
Input
nums = [1, 0, 2, 1, 0]Outputnums becomes [0, 0, 1, 1, 2]Two 0s, then two 1s, then one 2.
Example 2
Input
nums = [1, 2, 0]Outputnums becomes [0, 1, 2]Each color appears once.
Example 3
Input
nums = [2, 2, 1, 1]Outputnums becomes [1, 1, 2, 2]There are no 0s, so the 1s come first.
Constraints
0 ≤ len(nums) ≤ 105
Every item is 0, 1 or 2.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.