Problem Description

This problem asks you to sort an array containing only three distinct values: 0, 1, and 2. These numbers represent three colors - red (0), white (1), and blue (2). The goal is to rearrange the array in-place so that all elements of the same color are grouped together, following the specific order: all 0s first, then all 1s, and finally all 2s.

The key constraints are:

• You must modify the original array directly without using extra space for another array
• You cannot use built-in sorting functions
• The final arrangement must have all reds (0s) at the beginning, whites (1s) in the middle, and blues (2s) at the end

For example, if the input array is [2, 0, 2, 1, 1, 0], after sorting it should become [0, 0, 1, 1, 2, 2].

This is also known as the "Dutch National Flag Problem" because the Dutch flag consists of three horizontal bands of red, white, and blue colors.

Intuition

Since we only have three distinct values (0, 1, 2), we can think of partitioning the array into three regions. The key insight is that we don't need to sort in the traditional sense - we just need to group elements by their value.

Imagine maintaining three boundaries in the array:

• Everything to the left of one boundary should be 0s
• Everything to the right of another boundary should be 2s
• Everything in between should be 1s

We can achieve this with a single pass through the array by maintaining three pointers:

• Pointer i marks the rightmost position of the 0s region (initially -1 since no 0s are placed yet)
• Pointer j marks the leftmost position of the 2s region (initially at array length since no 2s are placed yet)
• Pointer k is our current scanning position

As we scan through the array with k:

• When we encounter a 0, we know it belongs at the beginning. We swap it with the element right after the last placed 0 (at position i+1), expand the 0s region by incrementing i, and move forward with k.
• When we encounter a 2, we know it belongs at the end. We swap it with the element right before the 2s region (at position j-1) and shrink the unprocessed region by decrementing j. We don't increment k here because the swapped element from position j-1 hasn't been examined yet.
• When we encounter a 1, it's already in the correct middle region, so we just move k forward.

This approach ensures that after one pass, all 0s are grouped at the beginning, all 2s at the end, and all 1s naturally fall in the middle.

Learn more about Two Pointers and Sorting patterns.

Solution Approach

The implementation uses the three-pointer technique described in the intuition. Let's walk through the algorithm step by step:

Initialization:

• Set i = -1 to mark the rightmost boundary of the 0s region (initially empty)
• Set j = len(nums) to mark the leftmost boundary of the 2s region (initially empty)
• Set k = 0 as the current scanning pointer starting from the beginning

Main Loop: The algorithm continues while k < j, meaning we still have unprocessed elements between the current position and the 2s region.

For each element at position k, we have three cases:

1. When nums[k] == 0:

   • Increment i by 1 to expand the 0s region
   • Swap nums[i] with nums[k] to place the 0 in the correct region
   • Increment k by 1 to move to the next element
   • We can safely increment k because we know the swapped element from position i was either a 0 (already processed) or a 1 (which is fine in the middle region)

2. When nums[k] == 2:

   • Decrement j by 1 to expand the 2s region from the right
   • Swap nums[j] with nums[k] to place the 2 in the correct region
   • Do NOT increment k because the element we just swapped from position j hasn't been examined yet

3. When nums[k] == 1:

   • Simply increment k by 1 since 1s belong in the middle region where they currently are

Final State: After the loop completes, the array is partitioned into three regions:

• [0, i]: Contains all 0s
• [i+1, j-1]: Contains all 1s
• [j, n-1]: Contains all 2s

This algorithm achieves O(n) time complexity with a single pass through the array and O(1) space complexity since we only use three pointer variables.

Example Walkthrough

Let's trace through the algorithm with the array [2, 0, 1, 2, 0].

Initial State:

• Array: [2, 0, 1, 2, 0]
• i = -1 (rightmost boundary of 0s region)
• j = 5 (leftmost boundary of 2s region)
• k = 0 (current scanning position)

Step 1: k = 0, nums[k] = 2

• Since we found a 2, decrement j to 4
• Swap nums[0] with nums[4]: [0, 0, 1, 2, 2]
• Keep k = 0 (don't increment since we need to examine the swapped element)

Step 2: k = 0, nums[k] = 0

• Since we found a 0, increment i to 0
• Swap nums[0] with nums[0] (no change): [0, 0, 1, 2, 2]
• Increment k to 1

Step 3: k = 1, nums[k] = 0

• Since we found a 0, increment i to 1
• Swap nums[1] with nums[1] (no change): [0, 0, 1, 2, 2]
• Increment k to 2

Step 4: k = 2, nums[k] = 1

• Since we found a 1, it's already in the correct middle region
• Simply increment k to 3

Step 5: k = 3, nums[k] = 2

• Since we found a 2, decrement j to 3
• Swap nums[3] with nums[3] (no change): [0, 0, 1, 2, 2]
• Keep k = 3

Termination: Now k = 3 and j = 3, so k < j is false. The loop ends.

Final Result: [0, 0, 1, 2, 2]

• Region [0, 1] contains all 0s
• Region [2, 2] contains all 1s
• Region [3, 4] contains all 2s

The array is successfully sorted with all colors grouped together in the correct order.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array. The algorithm uses a single pass through the array with the pointer k traversing from index 0 to index j. While k might not increment in every iteration (specifically when nums[k] == 2), each element is examined at most twice - once when k reaches it, and potentially once more if it's swapped from the right side. Since each element is processed a constant number of times, the overall time complexity remains linear.

The space complexity is O(1). The algorithm only uses three additional integer variables (i, j, and k) to track positions in the array, regardless of the input size. The sorting is performed in-place by swapping elements within the original array without requiring any additional data structures.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incrementing the current pointer after swapping with a 2

The Problem: A frequent mistake is incrementing the current pointer after swapping with an element from the right boundary when encountering a 2. This can lead to incorrect sorting because the element swapped from the right hasn't been examined yet.

Incorrect Code:

elif nums[current] == 2:
    right_boundary -= 1
    nums[right_boundary], nums[current] = nums[current], nums[right_boundary]
    current += 1  # WRONG! This skips examining the swapped element

Why It Fails: Consider the array [2, 0, 1]:

• When current = 0, we find nums[0] = 2
• We swap with nums[2], resulting in [1, 0, 2]
• If we increment current to 1, we skip examining the 1 that was just placed at index 0
• The final result would be [1, 0, 2] instead of [0, 1, 2]

Solution: Don't increment current after swapping with the right boundary. The swapped element needs to be examined in the next iteration.

elif nums[current] == 2:
    right_boundary -= 1
    nums[right_boundary], nums[current] = nums[current], nums[right_boundary]
    # Don't increment current - we need to examine the swapped element

Pitfall 2: Incorrect boundary initialization

The Problem: Initializing boundaries incorrectly can cause index out of bounds errors or infinite loops.

Common Mistakes:

# Mistake 1: Starting left_boundary at 0
left_boundary = 0  # WRONG! First swap would be nums[0] with nums[0]

# Mistake 2: Starting right_boundary at len(nums) - 1
right_boundary = len(nums) - 1  # WRONG! Would place first 2 at second-to-last position

Why It Fails:

• If left_boundary starts at 0, the first 0 encountered would increment it to 1 and swap with index 1, skipping index 0
• If right_boundary starts at len(nums) - 1, the first 2 would be placed at index len(nums) - 2, leaving the last position unprocessed

Solution: Initialize boundaries outside the array:

left_boundary = -1  # Before the array
right_boundary = len(nums)  # After the array

Pitfall 3: Using wrong loop condition

The Problem: Using current <= right_boundary instead of current < right_boundary can cause accessing already-processed elements in the 2s region.

Incorrect Code:

while current <= right_boundary:  # WRONG! May process elements already in 2s region

Why It Fails: When current == right_boundary, the element at that position has already been designated as part of the 2s region and shouldn't be processed again.

Solution: Use strict inequality:

while current < right_boundary:  # Correct - stops before the 2s region