MediumBlind75ArrayTwo PointersSort

Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue (0, 1, 2).

Examples

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

Sort in-place: 0s first, then 1s, then 2s.

Constraints

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

Approaches

Count occurrences of each color and overwrite the array.

CodeT: O(n) | S: O(1)
def sort_colors(nums):
    count = [0, 0, 0]
    for num in nums:
        count[num] += 1
    idx = 0
    for color in range(3):
        for _ in range(count[color]):
            nums[idx] = color
            idx += 1

First pass: move all 0s to the front. Second pass: move all 1s after the 0s.

CodeT: O(n) | S: O(1)
def sort_colors(nums):
    idx = 0
    for i in range(len(nums)):
        if nums[i] == 0:
            nums[idx], nums[i] = nums[i], nums[idx]
            idx += 1
    for i in range(idx, len(nums)):
        if nums[i] == 1:
            nums[idx], nums[i] = nums[i], nums[idx]
            idx += 1

Use three pointers: low for 0s, mid for current, high for 2s. Single pass.

Diagram

nums=[2,0,2,1,1,0] Dutch flag: low=0, mid=0, high=5 Swap 2 with high -> [0,0,2,1,1,2], high=4 Swap 0 with low -> [0,0,2,1,1,2], low=1,mid=1 ...continues until sorted: [0,0,1,1,2,2]
CodeT: O(n) | S: O(1)
def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

Complexity Comparison

Counting Sort
T: O(n)S: O(1)

Count occurrences of each color and overwrite the array.

Two Pass - Swap
T: O(n)S: O(1)

First pass: move all 0s to the front. Second pass: move all 1s after the 0s.

Dutch National Flag (Three Pointers)
T: O(n)S: O(1)

Use three pointers: low for 0s, mid for current, high for 2s. Single pass.

Common Mistakes

Using two separate passes when a single-pass solution exists

Not incrementing mid after swapping with low

Decrementing high before checking the swapped element

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems