Sort Colors

Q: What is the Dutch national flag problem?

Edsger Dijkstra posed it: arrange objects of three colors in a row, the red, white and blue of the Dutch flag, so each color is grouped, in one pass using only swaps. Sort Colors is the same problem with 0, 1 and 2, and his solution is the three-pointer partition.

Q: What is the time and space complexity of Sort Colors?

The one-pass solution runs in O(n) time, because every step shrinks the unread part by one cell. It uses O(1) extra space: three indices and a temporary value for the swap. Counting sort has the same bounds but reads the array twice.

Q: Is counting sort an acceptable answer for Sort Colors?

It meets the O(n) time and O(1) space bounds, and many interviewers accept it as a first answer. Expect to be asked for a single pass next. Counting is the better tool when there are many colors, since the partition only splits into three groups.

MediumTwo pointers Sorting

+10

You get an array nums in which every value is 0, 1 or 2: three colors, such as red, white and blue. Rearrange the array so that all the 0s come first, then all the 1s, then all the 2s, and return it. Solve it without a library sort function.

Function

sortColors(nums: integer-array) → integer-array

numsinteger-array: the colors, each one 0, 1 or 2
Returnsinteger-array: the same values with every 0 first, then every 1, then every 2

Constraints

1 ≤ nums.length ≤ 1.5 × 10⁴
Every nums[i] is 0, 1 or 2.
A color may be missing, and the array may hold a single color.

Examples

Input: nums = [2, 1, 0, 2, 0, 1, 1]
Output: [0, 0, 1, 1, 1, 2, 2]
Explanation: The array holds two 0s, three 1s and two 2s, so the result is exactly that: two 0s, then three 1s, then two 2s.

Follow-up

What would you change if there were k colors instead of three, with k much smaller than the length of the array?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Only 0, 1 and 2 can appear, so you can count them and rewrite the array in two passes. Three pointers that mark where the 0s end and where the 2s begin do it in one pass, putting every value in its place as you read it. That partition is the Dutch national flag algorithm.

Bubble sort by hand

Correct, but does not finish on the largest tests

Intuition

Without a library sort, the baseline is a sort you write yourself. Bubble sort walks the array and swaps any two neighbors that are out of order. Each pass carries the largest value it meets to the end, so after n-1 passes every position is final.

It makes about n²/2 comparisons: over 10^8 for n = 1.5 × 10^4, and none of them uses the fact that only three values exist.

Algorithm

Run n-1 passes over the array.
In each pass, compare every pair of neighbors nums[j] and nums[j + 1] that is not final yet, and swap them when the left one is bigger.
After pass number done (counting from 0), the last done + 1 positions hold their final values, so the next pass stops before them.
Return nums.

def sortColors(nums):
    n = len(nums)
    for done in range(n - 1):
        # One pass: the largest value left so far bubbles to index n-1-done.
        for j in range(n - 1 - done):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums

Count each color, then rewrite

Intuition

Equal values are interchangeable, so only the counts matter. In the first example, two 0s, three 1s and two 2s fix the answer before you move anything.

Read the array once to count each value, then overwrite it from the start: count[0] zeros, count[1] ones, count[2] twos. This is counting sort. Two passes and three counters give O(n) time and O(1) space.

Algorithm

Create three counters, all 0.
Read every value and add one to its counter.
Write count[0] zeros from the start, then count[1] ones, then count[2] twos.
Return nums.

def sortColors(nums):
    count = [0, 0, 0]  # how many 0s, 1s and 2s
    for x in nums:
        count[x] += 1
    i = 0
    for color in range(3):
        for _ in range(count[color]):
            nums[i] = color
            i += 1
    return nums

One pass with three pointers (Dutch national flag)

Intuition

Grow three regions while you read. Everything before low is 0, everything from low up to but not including mid is 1, everything after high is 2, and nums[mid] to nums[high] is unread.

Read nums[mid]. A 1 is already in its region, so move mid on. A 0 swaps with nums[low] and both move on: the value that comes back from low is a 1, or the same 0 when no 1 has been seen yet, so it is in place. A 2 swaps with nums[high] and high moves back, but mid stays, because the value that came from high is unread.

Every step moves mid forward or high back, so the loop ends after n steps. On [2, 0, 2] the first 2 swaps with the last and high drops to 1; index 0 still holds a 2, which swaps with the 0; the 0 then stays, giving [0, 2, 2].

Algorithm

Set low = 0, mid = 0 and high to the last index.
While mid ≤ high, read nums[mid].
If it is 0, swap it with nums[low] and move low and mid one step right.
If it is 1, move mid one step right.
If it is 2, swap it with nums[high] and move high one step left. Leave mid in place.
Return nums.

def sortColors(nums):
    # nums[:low] are 0s, nums[low:mid] are 1s, nums[high + 1:] are 2s.
    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:
            # The value swapped in from high is unread, so mid stays.
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
    return nums

Pitfalls and edge cases

Moving mid forward after a swap with high. The value that arrives is unread: on [1, 2, 0] the 2 swaps with the 0, and skipping the 0 returns [1, 0, 2].
Looping while mid < high. When the two meet, that cell is still unread: on [1, 0] the loop stops before it reads the 0 and returns [1, 0].
Letting high fall below zero with an unsigned index. An array of only 2s, like [2], drives high to -1, which underflows a Rust usize. Keep high one past the unread part instead.

Frequently asked questions3

What is the Dutch national flag problem?

Edsger Dijkstra posed it: arrange objects of three colors in a row, the red, white and blue of the Dutch flag, so each color is grouped, in one pass using only swaps. Sort Colors is the same problem with 0, 1 and 2, and his solution is the three-pointer partition.

What is the time and space complexity of Sort Colors?

The one-pass solution runs in O(n) time, because every step shrinks the unread part by one cell. It uses O(1) extra space: three indices and a temporary value for the swap. Counting sort has the same bounds but reads the array twice.

Is counting sort an acceptable answer for Sort Colors?

It meets the O(n) time and O(1) space bounds, and many interviewers accept it as a first answer. Expect to be asked for a single pass next. Counting is the better tool when there are many colors, since the partition only splits into three groups.

def sortColors(nums):
    # Write code here

Test #1

Test #2

Test #3

Argument

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

Expected Output

[0, 0, 1, 1, 1, 2, 2]

Sort Colors

Function

Constraints

Examples

Hints

Solution

Bubble sort by hand

Count each color, then rewrite

One pass with three pointers (Dutch national flag)

Pitfalls and edge cases

Frequently asked questions3

Similar problems