72. Sort Colors (Dutch National Flag)

Given an array nums with values 0, 1, and 2 representing red, white, and blue, sort them in-place so that all 0s come first, then 1s, then 2s.

You must solve it using a one-pass algorithm using only constant extra space.

Input: An integer array nums containing only 0, 1, and 2.

Output: The array sorted in-place as [0s, 1s, 2s].

Examples

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Explanation: Dutch National Flag: low tracks end of 0s, high tracks start of 2s, mid scans. After one pass: all 0s before 1s before 2s.

Input: [2,0,1]
Output: [0,1,2]
Explanation: Sorted directly.

Input: [0]
Output: [0]
Explanation: Single element, already sorted.

Constraints

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

Asked by