MediumArraysTwo PointersSorting

Sort Colors

2 approaches, code in every language

You are given an array whose entries are only the integers 0, 1, and 2, where each value stands for a color: red, white, and blue respectively. Rearrange the array in place so that every 0 comes first, then every 1, and finally every 2, keeping identical colors grouped together.

Solve it without leaning on a library sorting routine, and ideally in a single pass over the data using constant extra space.

Example 1

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

Output: [0,0,1,1,2,2]

All the reds move to the front, the whites to the middle, and the blues to the end.

Example 2

Input: nums = [2,0,1]

Output: [0,1,2]

Constraints

1 ≤ nums.length ≤ 300
nums[i] is one of 0, 1, or 2

Dutch National Flag (three pointers)

Sweep once with three pointers that partition the array into a zeros region, a ones region, and a twos region.

Loading animation…

Intuition

Picture the array as three growing zones: settled zeros on the left, settled twos on the right, and an unexplored middle. A single scanning pointer looks at each value and either drops it into the zeros zone by swapping left, leaves it in place as a one, or throws it into the twos zone by swapping right. Because a value swapped in from the right has not been examined yet, we re-inspect that position, but every 0 or 2 we place is final, so the whole thing finishes in one linear pass.

Algorithm walkthrough

1Keep three indices: low marks the next slot for a 0, high marks the next slot for a 2, and mid is the current position under inspection.
2While mid has not passed high, read nums[mid].
3If it is 0, swap it with nums[low] and advance both low and mid, since the swapped-in value was already checked.
4If it is 1, leave it in place and just advance mid.
5If it is 2, swap it with nums[high] and shrink high, but do not move mid because the incoming value still needs a look.

Implementation

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        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

Time

O(n)

Space

O(1)

Single pass with only constant extra memory.

Counting Sort (two passes)

Tally how many of each color exist, then rewrite the array straight from those tallies.

Intuition

Since there are only three distinct values, comparisons are unnecessary. One pass counts how many 0s, 1s, and 2s appear. A second pass then overwrites the array from left to right: first as many 0s as we counted, then the 1s, then the 2s. The array ends up sorted because the colors are emitted in ascending order.

Algorithm walkthrough

1Create a size-three tally array initialized to zero.
2Scan the input once, incrementing the tally for each value seen.
3Start an output index at the front of the array.
4For each color 0, then 1, then 2, write that color into the array as many times as its tally, advancing the output index each time.

Implementation

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        counts = [0, 0, 0]
        for value in nums:
            counts[value] += 1
        idx = 0
        for color in range(3):
            for _ in range(counts[color]):
                nums[idx] = color
                idx += 1

Time

O(n)

Space

O(1)

Two passes, but the tally has a fixed size so extra space stays constant.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Arrays

After the pattern

Now solve one you haven't seen.

Triage Band Ordering is our own problem on the technique behind Sort Colors: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free