75. Sort Colors - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Given an array nums with n objects colored red, white, or blue (represented by integers 0, 1, and 2 respectively), sort the array in-place so that objects of the same color are adjacent and appear in the order red, white, blue (i.e., all 0s, then all 1s, then all 2s).

Example 1:
- Input: nums = [2, 0, 2, 1, 1, 0]
- Output: [0, 0, 1, 1, 2, 2]
Example 2:
- Input: nums = [2, 0, 1]
- Output: [0, 1, 2]

Constraints:

n == nums.length
1 <= n <= 300
Each nums[i] is 0, 1, or 2.
The solution must be in-place (no extra array should be allocated for sorting).

Hints

Use a counting sort approach by first counting occurrences of each color, then overwriting the array.
A two-pass solution can simplify counting first and sorting next.
The Dutch National Flag algorithm provides an optimal one-pass solution using three pointers.

Approaches to Solve the Problem

Approach 1: Counting Sort (Two-Pass Solution)

Idea:
Count the number of 0s, 1s, and 2s in the array, then overwrite the array in order. First fill in all the 0s, then all the 1s, and finally the 2s. This satisfies the in-place requirement because we reuse the original array for the sorted output.

Complexity Analysis:

Time Complexity: O(n) – We iterate through the array twice (once to count, once to overwrite).
Space Complexity: O(1) – Only a fixed number of counters are used, regardless of array size.

Java Logic (Counting Sort):

public class Solution {
    public void sortColors(int[] nums) {
        int count0 = 0, count1 = 0, count2 = 0;
        // First pass: count occurrences
        for (int num : nums) {
            if (num == 0) count0++;
            else if (num == 1) count1++;
            else if (num == 2) count2++;
        }
        // Second pass: overwrite array based on counts
        int i = 0;
        while (count0-- > 0) nums[i++] = 0;
        while (count1-- > 0) nums[i++] = 1;
        while (count2-- > 0) nums[i++] = 2;
    }
}

Approach 2: Dutch National Flag Algorithm (Optimal One-Pass Solution)

Idea:
This classic approach uses three pointers (low, mid, and high) to partition the array into three sections for the three colors. The algorithm proceeds in a single pass through the array:

low tracks the position to place the next 0 (red).
high tracks the position to place the next 2 (blue).
mid is the current index being examined.

The algorithm works as follows:

Initialize low = 0, mid = 0, and high = n - 1 (start, current, and end pointers).
While mid <= high:
- If nums[mid] == 0 (red): swap it with nums[low], then increment both low and mid. (This moves the 0 to the front section.)
- If nums[mid] == 1 (white): leave it in place and just increment mid. (1s will naturally end up in the middle section.)
- If nums[mid] == 2 (blue): swap it with nums[high], then decrement high. (This moves the 2 to the end section. Do not increment mid in this case, because the element swapped from the end could be 0 or 1 and needs to be examined in the next iteration.)
Continue until mid passes high. At this point, all 0s will be before low, all 1s between low and high, and all 2s after high.

This in-place method ensures all 0s end up at the beginning, 1s in the middle, and 2s at the end, with only one pass through the array.

Complexity Analysis:

Time Complexity: O(n) – Each element is examined at most once and possibly swapped once, so the work is linear in the array size.
Space Complexity: O(1) – Only a few integer indices are used for tracking positions.

Java Code (Dutch National Flag algorithm):

Java

. . . .

Approach 3: Python Implementation (One-Pass Algorithm)

We can implement the same Dutch National Flag logic in Python. This approach is identical to Approach 2 but shown in Python for clarity:

Python3

. . . .

Step-by-Step Walkthrough (Example)

Let's walk through an example using the Dutch National Flag approach (Approach 2) to see how the pointers rearrange the array step by step. Consider the array nums = [2, 0, 2, 1, 1, 0]:

Initial state: low = 0, mid = 0, high = 5.
Array: [2, 0, 2, 1, 1, 0]
nums[mid] is 2 (blue), which belongs at the end. Swap nums[mid] with nums[high].
After swap: Array becomes [0, 0, 2, 1, 1, 2].
Update pointers: low = 0 (low stays the same since we swapped in a 0 at index 0), mid = 0 (we will re-check this index), high = 4 (moved one position left after placing a 2 at the end).
Next iteration: low = 0, mid = 0, high = 4.
Array: [0, 0, 2, 1, 1, 2]
nums[mid] is 0 (red), which belongs at the front. Swap nums[mid] with nums[low]. (Here, mid and low are both 0, so it's effectively a no-op swap.)
After swap: Array remains [0, 0, 2, 1, 1, 2].
Update pointers: low = 1 (move low right, as the position 0 is confirmed sorted), mid = 1 (move mid to the next position).
Next iteration: low = 1, mid = 1, high = 4.
Array: [0, 0, 2, 1, 1, 2]
nums[mid] is 0 again. Swap nums[mid] with nums[low] (swap index 1 with 1, which does nothing visible).
After swap: Array stays [0, 0, 2, 1, 1, 2].
Update pointers: low = 2, mid = 2.
Next iteration: low = 2, mid = 2, high = 4.
Array: [0, 0, 2, 1, 1, 2]
nums[mid] is 2 (blue). Swap it with nums[high] (swap index 2 with index 4).
After swap: Array becomes [0, 0, 1, 1, 2, 2]. (The 2 at index 2 and the 1 at index 4 have been swapped.)
Update pointers: low = 2 (unchanged), mid = 2 (stay to check the new element at index 2), high = 3 (decrement after placing a 2 at the end).
Next iteration: low = 2, mid = 2, high = 3.
Array: [0, 0, 1, 1, 2, 2]
nums[mid] is now 1 (white). This is the correct middle section value, so no swap needed.
Update pointers: mid = 3 (just move mid forward).
Next iteration: low = 2, mid = 3, high = 3.
Array: [0, 0, 1, 1, 2, 2]
nums[mid] is 1 again, which is fine in the middle.
Update pointers: mid = 4. Now mid (4) is greater than high (3), so the loop ends.

After these steps, the array is fully sorted as [0, 0, 1, 1, 2, 2]. This walkthrough demonstrates how the pointers low, mid, and high move and how swaps occur to partition the array into the three color regions in a single pass.

Common Mistakes and Edge Cases

Not handling edge cases: Make sure the algorithm works for scenarios like an array that is already sorted, an array of all zeros, or an array of all twos. The pointer approach should correctly handle these (e.g., if all elements are 2, low and mid will never move, and high will decrement until the loop ends).
Incorrect pointer updates: Be careful to update low, mid, and high correctly. For example, forgetting to increment mid when swapping a 0 to the front, or incorrectly incrementing mid when swapping a 2 to the end, can lead to missed elements or an infinite loop.
Using extra space: The problem requires sorting in-place. Copying the array to a new array to sort (except for the constant counters in Approach 1) would use extra space. Stick to the given array for sorting.
Swap logic errors: When implementing swaps, ensure you swap the correct indices. Off-by-one errors in the high index or swapping the wrong elements will produce incorrect results.

Alternative Variations

Sorting an array with k distinct elements: The Dutch National Flag algorithm generalizes to more than three categories, but it becomes more complex to manage multiple partitions. A counting sort approach can be extended to k distinct values by counting each and then writing them out in order. Another approach is to perform multiple passes of partition (for example, if there were four colors, you could partition into two groups repeatedly). This problem is essentially a special case of the general sorting problem where the range of values is small.
Sorting an array of 0s and 1s only: If the array contains only two distinct values (e.g., 0 and 1), the problem is simpler. You can use a two-pointer approach (one pointer at start for 0s, one at end for 1s) or just count the number of 0s and fill the array accordingly. This is like a simplified Dutch National Flag problem with two colors instead of three.

Sort an Array – LeetCode 912. (General array sorting using algorithms like QuickSort, MergeSort, etc.)
Sort List – LeetCode 148. (Sorting a linked list in O(n log n) time and constant space.)
Find the Kth Largest Element in an Array – LeetCode 215. (Related to partial sorting/selection algorithms; can be solved with quickselect or heaps.)