⚡Flashcard Drill➔
NeetCode #93LC-75MediumArrays & HashingNC 250
← Back to All Problems

#93 · #75 · Sort Colors(颜色分类)

📌 Problem Statement & Constraints

Given an array nums with n objects coloured red (0), white (1) or blue (2), sort them in place so that objects of the same colour are adjacent, in the order red, white, blue. You must solve it without using the library sort function, ideally in a single pass. Constraints: 1 <= n <= 300, nums[i] is 0, 1 or 2.

💡 Core Algorithmic Approaches

  1. Dutch national flag algorithm (Dijkstra): three pointers partition the array into four regions.
  2. Invariant: [0, low) is all 0s, [low, mid) is all 1s, (high, n-1] is all 2s, and [mid, high] is unexamined.
  3. Inspect nums[mid]: if it is 0, swap it into the 0-region (nums[low], nums[mid] = nums[mid], nums[low]) and advance both low and mid. If it is 1, just advance mid. If it is 2, swap it into the 2-region and decrement high without advancing mid -- the swapped-in element is unexamined.
  4. The loop runs while mid <= high, and each element is inspected once, giving a genuine single pass.

💻 Benchmark Python3 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] == 2
                nums[mid], nums[high] = nums[high], nums[mid]
                high -= 1                  # do NOT advance mid: new element unseen
        # regions: [0,low) = 0s, [low,mid) = 1s, (high,n-1] = 2s


# Counting sort: two passes, simpler to get right
class Solution2:
    def sortColors(self, nums: List[int]) -> None:
        cnt = [0, 0, 0]
        for x in nums:
            cnt[x] += 1
        i = 0
        for v in range(3):
            for _ in range(cnt[v]):
                nums[i] = v
                i += 1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) for both variants. The Dutch flag version makes exactly one pass; counting sort makes two.
💾 Space Complexity
O(1) for both -- only a handful of integer variables, versus a 3-element counter array.

⚠️ Interview Pitfalls & Follow-ups

  • Advancing mid after swapping a 2 to the back: the element swapped in from high has never been inspected, so mid must stay put. This is the single most common bug.
  • Using while mid < high: the last unexamined element is skipped. Use <=.
  • Swapping 0 to the front and incrementing only low: mid must also advance, because the element at mid after the swap is known to be a 1 (it came from the 1-region).
  • Writing a generic two-pass partition or a full quick sort: it works, but the point of the exercise is the three-way partition in one pass.
  • Returning the array: the signature returns None; the sort must happen in place.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems