LeetCode 75 - Sort Colors

LeetCode Problem 75

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Sorting

Solution

Problem Understanding

This problem asks us to sort an array that contains only three distinct values: 0, 1, and 2. These values represent colors:

• 0 represents red
• 1 represents white
• 2 represents blue

The goal is to rearrange the array so that all 0s come first, followed by all 1s, followed by all 2s.

The important requirement is that the sorting must be done in-place. This means we are not allowed to create another array to store the sorted result. Instead, we must modify the existing array directly.

For example, if the input is:

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

the sorted result should become:

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

The problem also explicitly forbids using the language's built-in sorting function. That means we must design our own algorithm.

The constraints are relatively small, since n <= 300, so even slower approaches would technically pass. However, the follow-up asks for a one-pass algorithm using constant extra space. This strongly hints that the intended solution is more algorithmically interesting than simply counting values or applying a generic sorting algorithm.

Several edge cases are important:

• Arrays containing only one element
• Arrays where all elements are identical
• Arrays already sorted
• Arrays sorted in reverse order
• Arrays with alternating colors
• Arrays missing one or two colors entirely

The problem guarantees that every value is either 0, 1, or 2, so we do not need to handle invalid inputs.

Approaches

Brute Force Approach

The most straightforward solution is to use a general sorting algorithm. Since built-in sorting is forbidden, we could implement something like bubble sort, selection sort, or insertion sort manually.

For example, with bubble sort, we repeatedly compare adjacent elements and swap them if they are out of order. Eventually, all smaller values move toward the front of the array.

This works because sorting algorithms guarantee that the array becomes ordered after enough comparisons and swaps.

However, this approach is inefficient. Bubble sort requires nested loops, leading to O(n²) time complexity. Even though the constraints are small enough for this to pass, it ignores the important observation that the array contains only three distinct values.

Better Observation

The key insight is that we do not need a full comparison-based sorting algorithm because the values are restricted to only 0, 1, and 2.

This allows us to partition the array into three regions:

• Left side contains all 0s
• Middle contains all 1s
• Right side contains all 2s

This is known as the Dutch National Flag algorithm.

Instead of repeatedly sorting elements, we maintain boundaries that track where each category belongs. By scanning the array once and swapping elements into the correct region, we can sort the array in linear time and constant space.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Uses repeated comparisons and swaps
Optimal	O(n)	O(1)	Uses three pointers and one pass

Algorithm Walkthrough

The optimal solution uses three pointers:

• left, tracks the position where the next 0 should go
• right, tracks the position where the next 2 should go
• current, scans through the array

The algorithm maintains these invariants:

• Everything before left is 0
• Everything after right is 2
• Everything between left and current - 1 is 1
• Everything from current onward is still unprocessed

Step-by-Step Process

1. Initialize three pointers.

Set:

• left = 0
• current = 0
• right = len(nums) - 1

Initially, the entire array is unprocessed. 2. Process elements while current <= right.

We stop once all elements have been classified into the correct regions. 3. If nums[current] == 0, place it into the left region.

Swap nums[current] with nums[left].

Then increment both:

• left += 1
• current += 1

This works because after placing a 0 correctly, everything before left remains valid. 4. If nums[current] == 1, leave it in the middle region.

Since 1s belong in the middle, no swap is needed.

Simply increment:

• current += 1

5. If nums[current] == 2, place it into the right region.

Swap nums[current] with nums[right].

Then decrement:

• right -= 1

Do not increment current yet.

This is important because the value swapped in from the right side has not been processed yet. 6. Continue until current > right.

At this point, all values are partitioned correctly.

Why it works

The algorithm maintains strict boundaries between processed regions and unprocessed elements.

At every step:

• All elements before left are guaranteed to be 0
• All elements after right are guaranteed to be 2
• All elements between left and current - 1 are guaranteed to be 1

Each operation either expands the left region, expands the right region, or advances through correctly placed 1s. Since every element is processed at most once, the algorithm terminates with the array fully sorted.

Python Solution

from typing import List

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        left = 0
        current = 0
        right = len(nums) - 1

        while current <= right:
            if nums[current] == 0:
                nums[left], nums[current] = nums[current], nums[left]
                left += 1
                current += 1

            elif nums[current] == 1:
                current += 1

            else:
                nums[current], nums[right] = nums[right], nums[current]
                right -= 1

The implementation directly follows the Dutch National Flag algorithm.

The left pointer tracks where the next 0 should be placed. The right pointer tracks where the next 2 should be placed. The current pointer scans through the array.

When the current value is 0, we swap it into the left region and move both pointers forward because both positions are now correctly processed.

When the current value is 1, it already belongs in the middle region, so we simply continue scanning.

When the current value is 2, we swap it with the right boundary and shrink the right region. We do not advance current because the swapped element still needs processing.

The algorithm modifies the input array directly and uses only constant extra space.

Go Solution

func sortColors(nums []int) {
    left := 0
    current := 0
    right := len(nums) - 1

    for current <= right {
        if nums[current] == 0 {
            nums[left], nums[current] = nums[current], nums[left]
            left++
            current++
        } else if nums[current] == 1 {
            current++
        } else {
            nums[current], nums[right] = nums[right], nums[current]
            right--
        }
    }
}

The Go implementation mirrors the Python solution closely.

Go slices behave similarly to dynamic arrays, so modifications inside the function affect the original array directly.

There are no integer overflow concerns because the indices remain within array bounds. Go also naturally handles empty or single-element slices correctly because the loop condition prevents invalid access.

Worked Examples

Example 1

Input:

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

Initial state:

Step	Array	left	current	right
Start	[2,0,2,1,1,0]	0	0	5

Iteration 1

nums[current] = 2

Swap with nums[right].

Step	Array	left	current	right
After swap	[0,0,2,1,1,2]	0	0	4

Iteration 2

nums[current] = 0

Swap with nums[left].

Step	Array	left	current	right
After swap	[0,0,2,1,1,2]	1	1	4

Iteration 3

nums[current] = 0

Swap with nums[left].

Step	Array	left	current	right
After swap	[0,0,2,1,1,2]	2	2	4

Iteration 4

nums[current] = 2

Swap with nums[right].

Step	Array	left	current	right
After swap	[0,0,1,1,2,2]	2	2	3

Iteration 5

nums[current] = 1

Move forward.

Step	Array	left	current	right
Move	[0,0,1,1,2,2]	2	3	3

Iteration 6

nums[current] = 1

Move forward.

Step	Array	left	current	right
Move	[0,0,1,1,2,2]	2	4	3

Loop ends because current > right.

Final result:

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

Example 2

Input:

[2,0,1]

Step	Array	left	current	right
Start	[2,0,1]	0	0	2
Swap 2 with right	[1,0,2]	0	0	1
Move past 1	[1,0,2]	0	1	1
Swap 0 with left	[0,1,2]	1	2	1

Final result:

[0,1,2]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed at most once
Space	O(1)	Only a few pointers are used

The algorithm performs a single pass through the array. Although some elements may participate in swaps multiple times, each pointer moves monotonically toward the center, ensuring linear overall work.

No additional arrays or data structures are allocated, so the extra space usage remains constant.

Test Cases

from typing import List

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        left = 0
        current = 0
        right = len(nums) - 1

        while current <= right:
            if nums[current] == 0:
                nums[left], nums[current] = nums[current], nums[left]
                left += 1
                current += 1
            elif nums[current] == 1:
                current += 1
            else:
                nums[current], nums[right] = nums[right], nums[current]
                right -= 1

solver = Solution()

nums = [2,0,2,1,1,0]
solver.sortColors(nums)
assert nums == [0,0,1,1,2,2]  # Provided example

nums = [2,0,1]
solver.sortColors(nums)
assert nums == [0,1,2]  # Provided example

nums = [0]
solver.sortColors(nums)
assert nums == [0]  # Single element

nums = [1]
solver.sortColors(nums)
assert nums == [1]  # Single middle value

nums = [2]
solver.sortColors(nums)
assert nums == [2]  # Single largest value

nums = [0,0,0]
solver.sortColors(nums)
assert nums == [0,0,0]  # All identical zeros

nums = [1,1,1]
solver.sortColors(nums)
assert nums == [1,1,1]  # All identical ones

nums = [2,2,2]
solver.sortColors(nums)
assert nums == [2,2,2]  # All identical twos

nums = [0,1,2]
solver.sortColors(nums)
assert nums == [0,1,2]  # Already sorted

nums = [2,1,0]
solver.sortColors(nums)
assert nums == [0,1,2]  # Reverse order

nums = [1,0,2,1,0,2]
solver.sortColors(nums)
assert nums == [0,0,1,1,2,2]  # Mixed ordering

nums = [2,2,1,1,0,0]
solver.sortColors(nums)
assert nums == [0,0,1,1,2,2]  # Grouped reverse order

nums = [1,0,1,0,1,0]
solver.sortColors(nums)
assert nums == [0,0,0,1,1,1]  # Missing twos

nums = [2,2,0,0]
solver.sortColors(nums)
assert nums == [0,0,2,2]  # Missing ones

Test	Why
[2,0,2,1,1,0]	Validates the standard mixed case
[2,0,1]	Small unsorted array
[0]	Minimum size input
[1]	Single middle value
[2]	Single largest value
[0,0,0]	All values identical
[1,1,1]	All middle values
[2,2,2]	All largest values
[0,1,2]	Already sorted input
[2,1,0]	Reverse sorted input
[1,0,2,1,0,2]	Random mixed arrangement
[2,2,1,1,0,0]	Reverse grouped arrangement
[1,0,1,0,1,0]	Missing one category
[2,2,0,0]	Missing middle values

Edge Cases

One important edge case is an array containing only one element. A naive implementation might accidentally perform unnecessary swaps or access invalid indices. In this implementation, the loop condition current <= right naturally handles single-element arrays correctly, and the algorithm exits safely after processing the lone value.

Another important case is when all elements are identical, such as [2,2,2]. Some incorrect implementations may repeatedly swap elements with themselves or fail to move pointers correctly, leading to infinite loops. This solution always updates either current or right, guaranteeing progress on every iteration.

A third critical edge case is arrays missing one of the three values, such as [1,1,0,0] or [2,2,0,0]. Some algorithms incorrectly assume all three categories exist and may mishandle boundaries. The Dutch National Flag approach works regardless of how many distinct values appear because it classifies elements dynamically during traversal.

Another subtle edge case is when a 2 is swapped from the current position with an unprocessed value from the right side. If we incorrectly increment current immediately after the swap, we may skip processing the incoming value. This implementation avoids that bug by keeping current in place after handling a 2.