What pattern does Sort Colors use?

The Pattern: Two Pointers (Three-Way Partitioning / Dutch National Flag) The Heuristic: Maintain three pointers to delimit the boundaries of each partition and move through the array once, swapping elements to their correct partitions on the fly, ensuring each element is processed at most once.

Sort Colors - LeetCode Solution & Explanation

Q: What is the time complexity of Sort Colors?

O(n). Each element is visited at most once by the pointer i. Swaps occur in constant time, and the pointers move inward without backtracking, resulting in a linear time complexity.

Problem

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. Use integers 0, 1, and 2 to represent the colors red, white, and blue respectively.

n == nums.length
1 ≤ n ≤ 300
nums[i] is 0, 1, or 2

Example

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

Output: [0,0,1,1,2,2]

The algorithm maintains three pointers: left, right, and i. Initially, left and i start at 0, and right starts at the last index. The pointer i traverses the array. When nums[i] is 0, it swaps with nums[left] and increments both left and i, ensuring all 0s are moved to the front. When nums[i] is 2, it swaps with nums[right] and decrements right, moving all 2s to the end. When nums[i] is 1, it simply moves forward. This process partitions the array into three sections in a single pass.

Approach

Straightforward Solution

A naive approach would count the number of 0s, 1s, and 2s in one pass, then overwrite the array in a second pass. This requires two passes and is less elegant. Alternatively, sorting the array directly is O(n log n), which is unnecessary given the limited range of values.

Core Observation

The problem requires partitioning the array into three distinct groups (0s, 1s, and 2s) in a single pass with constant space. This is a classic three-way partitioning problem where the relative order within each group does not matter.

Path to Optimal

The key insight is to use three pointers to maintain boundaries for the three groups. By moving through the array once and swapping elements to their correct partitions, the algorithm achieves O(n) time and O(1) space. The pointer i scans the array, left tracks the boundary of 0s, and right tracks the boundary of 2s. Swapping elements when encountering 0 or 2 ensures correct placement without revisiting elements unnecessarily.

Optimal Approach

Use the Dutch National Flag algorithm with three pointers: left, i, and right. Iterate while i <= right. If nums[i] == 0, swap with nums[left], increment left and i. If nums[i] == 2, swap with nums[right], decrement right but do not increment i because the swapped element needs evaluation. If nums[i] == 1, just increment i. This guarantees a single pass partitioning with constant space.

Time

O(n)

Each element is visited at most once by the pointer i. Swaps occur in constant time, and the pointers move inward without backtracking, resulting in a linear time complexity.

Space

O(1)

The algorithm uses only three integer pointers and performs swaps in-place, requiring constant auxiliary space.

Solution

1class Solution:
  def sortColors(self, nums: List[int]) -> None:
3
      left = 0
      right = len(nums) - 1
      i = 0
7
      while i <= right:
9
          if nums[i] == 0:
              nums[left], nums[i] = nums[i], nums[left]
              left += 1
              i += 1
14
          elif nums[i] == 2:
              nums[right], nums[i] = nums[i], nums[right]
              right -= 1
18
          else:
              i += 1

Step-by-Step Solution

1

Initialize Three Pointers to Partition the Array

4left = 0
5right = len(nums) - 1
6i = 0

Objective

To set up pointers that track the boundaries of the three partitions: 0s, 1s, and 2s.

Key Insight

The left pointer marks the boundary where all elements to its left are 0s. The right pointer marks the boundary where all elements to its right are 2s. The pointer i scans through the array to classify elements. This setup enables a single pass partitioning without extra space.

Interview Quick-Check

Core Logic

left and right pointers define the boundaries for 0s and 2s respectively, while i scans the array to place elements correctly.

State & Boundaries

left starts at 0, right at the last index, and i at 0 to cover the entire array.

2

Partition Array by Swapping Elements Based on Their Value

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

Objective

To iterate through the array and swap elements to their correct partitions using the three pointers.

Key Insight

When nums[i] is 0, swapping with nums[left] moves the 0 to the front, and both left and i advance because the swapped element at i is guaranteed to be processed. When nums[i] is 2, swapping with nums[right] moves the 2 to the end, and right moves inward, but i does not advance because the swapped element at i needs evaluation. When nums[i] is 1, it is already in the correct middle partition, so i advances. This logic ensures all elements are sorted in one pass.

Interview Quick-Check

Core Logic

Swapping 0s to the front and 2s to the back while scanning with i ensures a single pass partitioning.

State & Boundaries

The loop continues while i <= right to ensure all elements are processed.

Common Pitfalls & Bugs

Not decrementing right after swapping a 2 or incrementing i incorrectly can cause infinite loops or missed elements.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 11 Critical

nums[left], nums[i] = nums[i], nums[left]

Swap the current element with the element at the left pointer.

Swapping moves the 0 to the front partition, ensuring all 0s are grouped at the start of the array.

Line 16 Critical

nums[right], nums[i] = nums[i], nums[right]

Swap the current element with the element at the right pointer.

Swapping moves the 2 to the end partition, ensuring all 2s are grouped at the end of the array.

Line 10 Core

if nums[i] == 0:

Check if the current element is 0.

Identifying 0s is critical to move them to the front partition, maintaining the order red, white, blue.

Line 15 Core

elif nums[i] == 2:

Check if the current element is 2.

Identifying 2s is essential to move them to the end partition, maintaining the order red, white, blue.

Line 4 Core

left = 0

Initialize the left pointer at the start of the array.

The left pointer tracks the boundary where all elements to the left are 0s, enabling in-place partitioning of red color.

Line 5 Core

right = len(nums) - 1

Initialize the right pointer at the end of the array.

The right pointer tracks the boundary where all elements to the right are 2s, enabling in-place partitioning of blue color.

Line 8 Core

while i <= right:

Start a loop that continues while i is less than or equal to right.

The loop condition ensures all elements between left and right pointers are processed, covering the entire array in one pass.

Line 12 Core

left += 1

Increment the left pointer after placing a 0.

Advancing left updates the boundary of the 0 partition, preparing for the next 0 placement.

Line 13 Core

i += 1

Increment the scanning pointer i to continue processing.

Moving i forward after handling a 0 ensures the next element is evaluated, maintaining progress through the array.

Line 17 Core

right -= 1

Decrement the right pointer after placing a 2.

Moving right inward updates the boundary of the 2 partition, preparing for the next 2 placement.

Line 19 Core

else:

Handle the case where the current element is 1 by moving the scanning pointer forward.

Since 1s belong in the middle partition, no swap is needed; simply advancing i continues the scan.

Line 20 Core

i += 1

Increment the scanning pointer i to continue processing.

Advancing i after encountering a 1 ensures the algorithm progresses through the array without unnecessary swaps.

Line 6 Standard

i = 0

Initialize the scanning pointer i at the start of the array.

Pointer i scans through the array to classify elements and swap them into correct partitions.

Test Your Understanding

Why does the pointer i not increment after swapping with the right pointer when nums[i] == 2?

Because the element swapped from the right end has not been evaluated yet, so i must stay to check this new element to ensure it is correctly placed.

Don't just read it. Drill it.

Reconstruct Sort Colors from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Sort Colors drill

or drill a free problem

1	`class Solution:`
2	`def sortColors(self, nums: List[int]) -> None:`
3
4	`left = 0`
5	`right = len(nums) - 1`
6	`i = 0`
7
8	`while i <= right:`
9
10	`if nums[i] == 0:`
11	`nums[left], nums[i] = nums[i], nums[left]`
12	`left += 1`
13	`i += 1`
14
15	`elif nums[i] == 2:`
16	`nums[right], nums[i] = nums[i], nums[right]`
17	`right -= 1`
18
19	`else:`
20	`i += 1`

8	`while i <= right:`
10	`if nums[i] == 0:`
11	`nums[left], nums[i] = nums[i], nums[left]`
12	`left += 1`
13	`i += 1`
15	`elif nums[i] == 2:`
16	`nums[right], nums[i] = nums[i], nums[right]`
17	`right -= 1`
19	`else:`
20	`i += 1`