How do you solve Sort Colors?

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.

Sort Colors

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.

Q: 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.

Medium Two Pointers

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

Preview

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…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use the Dutch National Flag algorithm with three pointers: left, i, and right. Iterate while i <= right…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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.

Pattern Spotlight

Two Pointers (Three-Way Partitioning / Dutch National Flag)

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.

Solution

Python

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

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.

Partition Array by Swapping Elements Based on Their Value

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

1 more step with full analysis available on Pro.

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.

Full line-by-line criticality + rationale for all 13 lines available on Pro.

Test Your Understanding

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

See the answer with Pro.

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`