Back to ArraysSort Colors
Medium

Sort Colors

MediumMust DoDutch National FlagTwo Pointers

Given an array containing only the values 0, 1 and 2, sort it in place in a single pass without using a separate counting or sorting step.

Examples

Example 1

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

Explanation: All 0s move to the front, all 2s move to the back, and the 1s settle in between — in one pass.

Example 2

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

Explanation: An already-sorted input is left untouched.

Example 3

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

Explanation: A single repeated color needs no swaps at all.

Constraints

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

Follow-up

How would you generalize this one-pass partition to k distinct integer values instead of exactly 3?

Loading editor…

Code execution is coming soon.