Sort Colors - Quicksort Partition - Leetcode 75 - Python

Main ideas / lessons

• “Sort Colors” problem: Given an array nums containing only {0, 1, 2}, sort it in ascending order so that:

  • all 0s come first,
  • then all 1s,
  • then all 2s.

• The speaker emphasizes efficiency and why generic sorting is overkill:

  • Standard library/general sorting is typically O(n log n).
  • Since there are only three distinct values, more specialized solutions exist.

• Two core approaches are discussed:

Methodology / instructions (detailed steps)

Approach 1: Bucket/counting (linear time)

Idea: Count how many of each value appear, then overwrite the array in-place.

1. Create counters for the three values:

   • count0, count1, count2 (conceptually three “buckets” or a tiny map/array)

2. First scan:

   • For each element in nums, increment the corresponding counter.

3. Second phase: overwrite in-place:

   • Write count0 zeros at the beginning.
   • Write count1 ones immediately after the zeros.
   • Write count2 twos at the end.

Complexity (as claimed):

• Time: O(n)
• Extra space: O(1) (only three counters)

---

Approach 2: One-pass partition (Dutch National Flag–style)

Goal: Partition the array in one scan into three regions:

• Left region: all 0s
• Middle region: all 1s
• Right region: all 2s

Pointers

• left = start index (initially 0)
• right = end index (initially len(nums) - 1)
• i = scanning index (runs while i <= right)

Loop condition

• While i <= right, process nums[i].

In-place swap logic

• Use a helper swap that swaps values directly inside the array, e.g. swapping nums[i] and nums[j].

Case handling for nums[i]

• If nums[i] == 0:

  • Swap nums[i] with nums[left]
  • Increment left by 1
  • Allow i to increment normally via the loop
  • Rationale: left tracks a region where values should ultimately be 1/unprocessed, so inserting a 0 there is safe.

• If nums[i] == 2:

  • Swap nums[i] with nums[right]
  • Decrement right by 1
  • Do not advance i immediately after the swap
  • Rationale (edge case):
    • Swapping with right may bring a new, unprocessed value into position i.
    • If the incoming value is 0, it must be handled—so i must be re-checked.

• If nums[i] == 1:

  • Do nothing besides letting the loop move on (i increments normally)
  • Rationale: ones belong in the middle region.

Termination

• Stop when i surpasses right.

At that point:

• everything left of left is 0,
• everything right of right is 2,
• the remaining middle section is 1s.

Example result: 0,0,1,1,2,2

Speakers / sources featured

• Speaker: “hey everyone welcome back…” (unnamed presenter/channel host)
• Referenced concepts/algorithms:
  • quicksort’s partition concept
  • bucket sort/counting concept
  • LeetCode problem: “Sort Colors” / “Leetcode 75”