#75

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Sort Colors

Sort Colors requires in-place reordering of an array using a two-pointer scanning strategy to group 0s, 1s, and 2s efficiently.

array two pointers sorting

Problem Statement

You are given an array nums containing n objects colored red, white, or blue, represented by 0, 1, and 2 respectively. The goal is to sort the array in-place so that objects of the same color are adjacent, in the order red (0), white (1), and blue (2). Using built-in sorting functions is prohibited, and the solution must rearrange the elements without allocating another array.

The challenge emphasizes scanning with two pointers while tracking invariants: all elements before the first pointer are 0s, all elements after the second pointer are 2s, and 1s naturally occupy the middle. Handling swaps correctly is crucial to avoid overwriting unsorted values. Arrays may vary in length from 1 to 300, and every element is guaranteed to be 0, 1, or 2, creating a predictable but sensitive swapping pattern.

Examples

Example 1

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

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

Example details omitted.

Example 2

Input: nums = [2,0,1]

Output: [0,1,2]

Example details omitted.

Constraints

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

Solution Approach

Two-Pointer Invariant Scanning

Use two pointers, low and high, to scan the array while maintaining three partitions: elements before low are all 0s, elements after high are all 2s, and the middle contains 1s. Iterate through the array with an index i, swapping values to the correct partition whenever a 0 or 2 is encountered. This approach ensures all swaps respect the invariant, moving colors to their correct positions without extra space, and naturally leaves 1s in place. The key is adjusting indices correctly after each swap to avoid reprocessing elements.

Counting Approach for Two Pass

As a simpler alternative, perform a two-pass counting sort by first counting the number of 0s, 1s, and 2s, then overwriting the array according to these counts. While this uses two passes, it avoids complex swap logic and still operates in-place with O(n) time. This approach demonstrates the failure mode of overcomplicating swaps when a straightforward counting method can solve the problem efficiently. It also helps verify correctness against the single-pass two-pointer approach.

Invariant Checks and Edge Handling

During iteration, continuously check the partition invariants to avoid misplacing colors, particularly when 0s or 2s appear consecutively. Edge cases include arrays with all identical colors, alternating patterns, or single-element arrays. Ensuring i does not overshoot high and swapping elements correctly prevents infinite loops and misplaced elements. Proper handling of these scenarios strengthens understanding of the two-pointer invariant pattern, highlighting the precise pointer updates required for reliable in-place sorting.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The two-pointer scanning solution operates in O(n) time since each element is visited at most once, and O(1) additional space as all operations are performed in-place. The two-pass counting method also runs in O(n) time but still requires only constant extra space for counting variables. Both approaches ensure linear performance for the constrained array sizes of 1 to 300 elements, satisfying the problem's efficiency requirements.

What Interviewers Usually Probe

Do you correctly maintain the low, mid, and high pointers to enforce the invariant?
Can you handle arrays where all elements are the same or already partially sorted?
Will you update indices carefully after each swap to avoid overwriting unsorted values?

Common Pitfalls or Variants

Common pitfalls

Swapping a 0 or 2 without updating the current index can skip elements or cause infinite loops.
Failing to maintain the invariant partitions correctly can mix colors and require multiple passes.
Edge cases like single-element arrays or arrays with only one color may break naive implementations if not handled.

Follow-up variants

Sort Colors II: Extend the problem to k colors represented by integers 0 to k-1, still requiring in-place ordering.
Dutch National Flag Variant: Separate an array into three partitions based on a pivot value, testing invariant tracking under different rules.
Sort Colors with Stability: Sort the array while preserving the relative order of 1s to test the effect on two-pointer swaps.

FAQ

How does the two-pointer scanning pattern work in Sort Colors?

Two-pointer scanning divides the array into partitions for 0s, 1s, and 2s. Swaps move colors to the correct partition while maintaining invariant positions, ensuring in-place sorting with O(n) time and O(1) space.

Can I use Python's sort function for this problem?

No, using built-in sorting functions is prohibited. The problem requires explicitly rearranging elements using in-place strategies like two-pointer scanning or counting methods.

What is the main advantage of the single-pass approach over two-pass counting?

Single-pass two-pointer scanning avoids iterating over the array multiple times, efficiently maintaining partition invariants and moving each element directly to its correct position.

How do I handle edge cases such as arrays with all identical colors?

Edge cases require careful pointer handling. If all elements are the same, swaps may not occur, but the invariant tracking still ensures correct partitions without errors or infinite loops.

Why is it important to update indices carefully after each swap?

Incorrect index updates can cause skipped elements or repeated swaps, violating the partition invariant and producing incorrect final order, which is a common failure mode for this problem.

terminal

Solution

Solution 1: Three Pointers

We define three pointers $i$, $j$, and $k$. Pointer $i$ is used to point to the rightmost boundary of the elements with a value of $0$ in the array, and pointer $j$ is used to point to the leftmost boundary of the elements with a value of $2$ in the array. Initially, $i=-1$, $j=n$. Pointer $k$ is used to point to the current element being traversed, initially $k=0$.

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        i, j, k = -1, len(nums), 0
        while k < j:
            if nums[k] == 0:
                i += 1
                nums[i], nums[k] = nums[k], nums[i]
                k += 1
            elif nums[k] == 2:
                j -= 1
                nums[j], nums[k] = nums[k], nums[j]
            else:
                k += 1

Continue Practicing

#88 merge sorted array #18 4sum #16 3sum closest