Sort Colors

Medium~15 min

Given an array nums containing only the values 0, 1, and 2 (representing red, white, and blue), sort the array in-place so that all 0s come first, then all 1s, then all 2s.

This is known as the Dutch National Flag problem, named after the three-colored flag of the Netherlands.

You should solve this in a single pass with O(1) extra space. Do not use a library sort function.

Return the sorted array.

Examples

Example 1
Input: nums = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]
Explanation: All 0s moved to the front, then 1s, then 2s.
Example 2
Input: nums = [2, 0, 1]
Output: [0, 1, 2]
Explanation: Each color appears once, sorted in order.
Example 3
Input: nums = [0]
Output: [0]
Explanation: Single element is already sorted.

Constraints

  • 1 <= nums.length <= 300
  • nums[i] is 0, 1, or 2
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run