Sort Colors

LeetCode 75: Sort Colors Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses three pointers to partition the array into three distinct regions (0s, 1s, and 2s) in a single pass, swapping elements into their correct positions in-place.

The "Sort Colors" problem requires sorting an array nums containing n objects colored red, white, or blue. These colors are represented by the integers 0, 1, and 2, respectively. The goal is to sort the array in-place so that objects of the same color are adjacent, following the order red (0), white (1), and blue (2). This is a classic interview question often found in the LeetCode 75 study plan.

The constraints strictly forbid using the library's built-in sort function and suggest finding a one-pass algorithm using constant extra space.

Brute Force Approach for Sort Colors

A naive brute force approach would be to treat this as a generic sorting problem without leveraging the fact that there are only three distinct values. One might simply implement a standard sorting algorithm like Bubble Sort or use a library function (though prohibited by the problem statement for the optimal solution).

Another common sub-optimal approach is a two-pass "Counting Sort" logic:

1. Iterate through the array to count the number of 0s, 1s, and 2s.
2. Iterate through the array a second time to overwrite the array indices based on the counts (e.g., fill the first count0 indices with 0, the next count1 indices with 1, etc.).

Pseudo-code (Counting Approach):

count0 = 0, count1 = 0, count2 = 0
for x in nums:
    increment count of x

index = 0
for i from 0 to count0: nums[index++] = 0
for i from 0 to count1: nums[index++] = 1
for i from 0 to count2: nums[index++] = 2

Complexity Analysis:

• Time Complexity: $O(N \log N)$ for generic sort, or $O(2N)$ for the two-pass counting approach.
• Space Complexity: $O(1)$ or $O(\log N)$ depending on the sort implementation.

Why it fails: While the counting approach is technically $O(N)$, it requires two passes over the data. The problem's follow-up explicitly asks for a one-pass algorithm. Furthermore, generic sorting does not utilize the limited cardinality of the input elements (only 3 values).

Algorithm Strategy: Two Pointer Patterns

1. Initialization:

   • Initialize low at the start of the array (index 0).
   • Initialize high at the end of the array (index n-1).
   • Initialize mid at the start of the array (index 0).

2. Traversal:

   • Loop while mid is less than or equal to high. This ensures we process every element that hasn't been placed in the 2s region yet.

3. Decision Logic (at nums[mid]):

   • Case 0: If the current element is 0, it belongs in the Left Region. Swap nums[mid] with nums[low]. Increment both low and mid.
   • Case 1: If the current element is 1, it is already in the correct relative position (Middle Region). Simply increment mid.
   • Case 2: If the current element is 2, it belongs in the Right Region. Swap nums[mid] with nums[high]. Decrement high. Crucial: Do not increment mid here, because the element swapped from high has not been inspected yet and could be a 0 or 2.

4. Termination:

   • The process ends when mid crosses high. At this point, all boundaries meet, and the array is fully partitioned.

Execution Flow

Consider nums = [2, 0, 2, 1, 1, 0].

1. Start: low=0, mid=0, high=5.

   • nums[mid] is 2.
   • Swap nums[0] and nums[5]. Array: [0, 0, 2, 1, 1, 2].
   • Decrement high to 4. mid stays 0.

2. Step 2: low=0, mid=0, high=4.

   • nums[mid] is 0.
   • Swap nums[0] and nums[0] (self-swap). Array: [0, 0, 2, 1, 1, 2].
   • Increment low to 1, mid to 1.

3. Step 3: low=1, mid=1, high=4.

   • nums[mid] is 0.
   • Swap nums[1] and nums[1]. Array: [0, 0, 2, 1, 1, 2].
   • Increment low to 2, mid to 2.

4. Step 4: low=2, mid=2, high=4.

   • nums[mid] is 2.
   • Swap nums[2] and nums[4]. Array: [0, 0, 1, 1, 2, 2].
   • Decrement high to 3. mid stays 2.

5. Step 5: low=2, mid=2, high=3.

   • nums[mid] is 1.
   • Increment mid to 3.

6. Step 6: low=2, mid=3, high=3.

   • nums[mid] is 1.
   • Increment mid to 4.

7. End: mid (4) > high (3). Loop terminates. Result: [0, 0, 1, 1, 2, 2].

Proof of Correctness

The correctness relies on the loop invariant involving the three partitions.

• Invariant: [0, low) contains 0s, (high, n-1] contains 2s, and [low, mid) contains 1s.
• Initialization: Initially, all ranges are empty, so the invariant holds trivially.
• Maintenance:
  • When we see a 0, we swap it to low, extending the 0s range and shifting the 1s range.
  • When we see a 1, we extend the 1s range by moving mid.
  • When we see a 2, we swap it to high, extending the 2s range.
• Termination: Since mid increases or high decreases at every step, the unclassified window [mid, high] shrinks to zero. When the loop finishes, the entire array is covered by the three sorted partitions.

Pattern Reuse Notes

The "Two Pointers - In-place Array Modification" pattern is highly versatile. Understanding how to partition arrays using pointers is essential for the following problems:

• LeetCode 26: Remove Duplicates from Sorted Array - Uses a read/write pointer pair to partition unique elements from duplicates.
• LeetCode 27: Remove Element - Uses pointers to separate target values from the rest of the array.
• LeetCode 80: Remove Duplicates from Sorted Array II - An extension of LeetCode 26 allowing at most two duplicates.
• LeetCode 283: Move Zeroes - Essentially a simplified version of Sort Colors where we partition 0s and non-0s.

Reference Implementation

C++ Solution for LeetCode 75

1class Solution {
2public:
3    void sortColors(vector<int>& nums) {
4        int low = 0;
5        int mid = 0;
6        int high = nums.size() - 1;
7
8        while (mid <= high) {
9            if (nums[mid] == 0) {
10                // Swap current element to the 0s boundary
11                swap(nums[low], nums[mid]);
12                low++;
13                mid++;
14            } else if (nums[mid] == 1) {
15                // 1s are in the middle, just move forward
16                mid++;
17            } else {
18                // Swap current element to the 2s boundary
19                swap(nums[mid], nums[high]);
20                high--;
21                // Do not increment mid; we need to check the swapped value
22            }
23        }
24    }
25};

Java Solution for LeetCode 75

1class Solution {
2    public void sortColors(int[] nums) {
3        int low = 0;
4        int mid = 0;
5        int high = nums.length - 1;
6
7        while (mid <= high) {
8            if (nums[mid] == 0) {
9                int temp = nums[low];
10                nums[low] = nums[mid];
11                nums[mid] = temp;
12                low++;
13                mid++;
14            } else if (nums[mid] == 1) {
15                mid++;
16            } else {
17                int temp = nums[high];
18                nums[high] = nums[mid];
19                nums[mid] = temp;
20                high--;
21                // Note: mid is NOT incremented here
22            }
23        }
24    }
25}

Python Solution for LeetCode 75

1class Solution:
2    def sortColors(self, nums: List[int]) -> None:
3        """
4        Do not return anything, modify nums in-place instead.
5        """
6        low, mid, high = 0, 0, len(nums) - 1
7
8        while mid <= high:
9            if nums[mid] == 0:
10                nums[low], nums[mid] = nums[mid], nums[low]
11                low += 1
12                mid += 1
13            elif nums[mid] == 1:
14                mid += 1
15            else: # nums[mid] == 2
16                nums[high], nums[mid] = nums[mid], nums[high]
17                high -= 1
18                # Do not increment mid here