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
- Dutch national flag algorithm (Dijkstra): three pointers partition the array into four regions.
- Invariant:
[0, low)is all 0s,[low, mid)is all 1s,(high, n-1]is all 2s, and[mid, high]is unexamined. - Inspect
nums[mid]: if it is 0, swap it into the 0-region (nums[low], nums[mid] = nums[mid], nums[low]) and advance bothlowandmid. If it is 1, just advancemid. If it is 2, swap it into the 2-region and decrementhighwithout advancingmid-- the swapped-in element is unexamined. - 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
midafter swapping a 2 to the back: the element swapped in fromhighhas never been inspected, somidmust 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:midmust also advance, because the element atmidafter 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.