LeetCode 75: Sort Colors Solution in Python Explained

Problem Statement

LeetCode 75, Sort Colors, is a medium-level problem where you’re given an array nums containing (n) integers, each representing a color: 0 (red), 1 (white), or 2 (blue). Your task is to sort the array in-place so that all 0s come first, followed by all 1s, then all 2s, using O(1) extra space and a single pass if possible. This is also known as the Dutch National Flag problem.

Constraints

n == nums.length: Array length.
1 <= n <= 300: Length is between 1 and 300.
nums[i] is either 0, 1, or 2.

Example

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Explanation: Sort colors in-place: all 0s, then 1s, then 2s.

Input: nums = [2,0,1]
Output: [0,1,2]
Explanation: Sort [2,0,1] into [0,1,2].

Input: nums = [0]
Output: [0]
Explanation: Single element, already sorted.

Understanding the Problem

How do you solve LeetCode 75: Sort Colors in Python? For nums = [2,0,2,1,1,0], sort it in-place to [0,0,1,1,2,2] with all 0s first, then 1s, then 2s, using minimal extra space. Since there are only three values, we can optimize beyond general sorting algorithms. We’ll explore two approaches: a Dutch National Flag Solution (optimal and primary) and an Alternative with Counting Sort (intuitive but uses extra passes). The Dutch Flag method runs in O(n) time with O(1) space, sorting in a single pass.

Solution 1: Dutch National Flag Approach (Primary)

Explanation

Use three pointers: left (for 0s), right (for 2s), and curr (current index). Traverse the array with curr:

If nums[curr] = 0, swap with left, increment both left and curr.
If nums[curr] = 1, just increment curr.
If nums[curr] = 2, swap with right, decrement right (don’t increment curr yet, as swapped value needs checking).

This partitions the array into 0s, 1s, and 2s in one pass.

Here’s a flow for [2,0,2,1,1,0]:

Initial: [2,0,2,1,1,0], left=0, curr=0, right=5
curr=0, 2 -> swap with right, [0,0,2,1,1,2], right=4
curr=0, 0 -> swap with left, [0,0,2,1,1,2], left=1, curr=1
curr=1, 0 -> swap with left, [0,0,2,1,1,2], left=2, curr=2
curr=2, 2 -> swap with right, [0,0,1,1,2,2], right=3
curr=2, 1 -> curr=3
curr=3, 1 -> curr=4, done
Result: [0,0,1,1,2,2]

Initialize Pointers.

left = 0, right = n-1, curr = 0.

Single Pass.

Partition based on 0, 1, 2 values.

Swap and Move.

Adjust pointers and swap as needed.

Modify In-Place.

Step-by-Step Example

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

We need [0,0,1,1,2,2].

Goal: Sort colors in-place.
Result for Reference: [0,0,1,1,2,2].
Start: nums = [2,0,2,1,1,0], left = 0, curr = 0, right = 5.
Step 1: curr = 0, nums[0] = 2.

Swap with right: [0,0,2,1,1,2], right = 4.

Step 2: curr = 0, nums[0] = 0.

Swap with left: [0,0,2,1,1,2], left = 1, curr = 1.

Step 3: curr = 1, nums[1] = 0.

Swap with left: [0,0,2,1,1,2], left = 2, curr = 2.

Step 4: curr = 2, nums[2] = 2.

Swap with right: [0,0,1,1,2,2], right = 3.

Step 5: curr = 2, nums[2] = 1.

curr = 3.

Step 6: curr = 3, nums[3] = 1.

curr = 4.

Step 7: curr = 4 > right = 3, stop.
Finish: nums = [0,0,1,1,2,2], sorted in-place.

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

We need [0,1,2].

Start: left = 0, curr = 0, right = 2.
Step 1: curr = 0, 2 -> swap with right: [1,0,2], right = 1.
Step 2: curr = 0, 1 -> curr = 1.
Step 3: curr = 1, 0 -> swap with left: [0,1,2], left = 1, curr = 2.
Step 4: curr = 2 > right = 1, stop.
Finish: nums = [0,1,2].

How the Code Works (Dutch National Flag)

Here’s the Python code with line-by-line explanation:

def sortColors(nums: list[int]) -> None:
    # Line 1: Initialize pointers
    left = 0
    right = len(nums) - 1
    curr = 0

    # Line 2: Single pass with three pointers
    while curr <= right:
        if nums[curr] == 0:
            # Line 3: Swap with left for 0
            nums[curr], nums[left] = nums[left], nums[curr]
            left += 1
            curr += 1
        elif nums[curr] == 1:
            # Line 4: Move past 1
            curr += 1
        else:  # nums[curr] == 2
            # Line 5: Swap with right for 2
            nums[curr], nums[right] = nums[right], nums[curr]
            right -= 1

    # Line 6: Array sorted in-place

Alternative: Counting Sort Approach

Explanation

Count the occurrences of 0, 1, and 2, then overwrite the array with the correct number of each value in order. This uses O(1) space for three counters but requires two passes, not meeting the single-pass preference.

Count Colors.

Tally 0s, 1s, 2s.

Rewrite Array.

Fill with 0s, then 1s, then 2s.

Modify In-Place.

Step-by-Step Example (Alternative)

For [2,0,2,1,1,0]:

Start: zeros = 0, ones = 0, twos = 0.
Step 1: Count.

2: twos = 1.
0: zeros = 1.
2: twos = 2.
1: ones = 1.
1: ones = 2.
0: zeros = 2.
Result: zeros = 2, ones = 2, twos = 2.

Step 2: Rewrite.

[0,0] (2 zeros), [0,0,1,1] (2 ones), [0,0,1,1,2,2] (2 twos).

Finish: nums = [0,0,1,1,2,2].

How the Code Works (Counting Sort)

def sortColorsCount(nums: list[int]) -> None:
    # Line 1: Count occurrences
    zeros = ones = twos = 0
    for num in nums:
        if num == 0:
            zeros += 1
        elif num == 1:
            ones += 1
        else:
            twos += 1

    # Line 2: Rewrite array
    for i in range(len(nums)):
        if i < zeros:
            nums[i] = 0
        elif i < zeros + ones:
            nums[i] = 1
        else:
            nums[i] = 2

Complexity

Dutch National Flag:

Time: O(n) – Single pass through array.
Space: O(1) – Three pointers.

Counting Sort:

Time: O(n) – Two passes (count and write).
Space: O(1) – Three counters.

Efficiency Notes

Dutch National Flag is O(n) time and O(1) space, optimal for LeetCode 75 with a single pass, meeting all requirements. Counting Sort is also O(n) time and O(1) space but uses two passes, making it less efficient in terms of passes but simpler to understand.

Key Insights

Tips to master LeetCode 75:

Three Pointers: Partition with left, curr, right.
Single Pass: Sort in-place efficiently.
Swap Logic: Handle 2s carefully due to swapped values.

Additional Example

For nums = [1,2,0]:

Goal: [0,1,2].
Dutch: [0,2,1] -> [0,1,2], return [0,1,2].
Result: [0,1,2].

Edge Cases

Single Element: [1] – Already sorted.
All Same: [0,0,0] – No swaps needed.
Max Length: 300 elements – Handled efficiently.

Final Thoughts

The Dutch National Flag solution is a stellar choice for LeetCode 75 in Python—fast, in-place, and elegant, perfect for three-value sorting. For a related challenge, try LeetCode 74: Search a 2D Matrix to switch to searching! Ready to sort? Solve LeetCode 75 on LeetCode now and test it with [2,0,2,1,1,0] or [2,0,1] to master color sorting. Dive in and paint the array!