Dutch National Flag

Given an array nums containing only the integers 0, 1, and 2, sort the array in place so that all 0s come first, then all 1s, then all 2s.

You must solve this in a single pass over the array using O(1) extra space — you may not use a library sort function, and you should avoid counting occurrences in a separate pass (a two-pass counting solution works but misses the point of this problem).

Example 1

Input: nums = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]

Example 2

Input: nums = [2, 0, 1]
Output: [0, 1, 2]

Constraints

• 1 <= nums.length <= 300
• nums[i] is 0, 1, or 2.