Sort Colors

Problem Link

75. Sort Colors – LeetCode

Problem Statement

You are given an array nums with n objects colored red, white, or blue, represented as integers:

0 → red
1 → white
2 → blue

Sort them in-place so that objects of the same color are adjacent, with the colors in the order: red → white → blue.

Examples

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

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

Follow-up

Can you solve it in one pass using constant extra space?

Intuition

This is a variant of the Dutch National Flag Problem:

0 → red
1 → white
2 → blue

We maintain three regions:

Left region of all 0s
Middle region of all 1s
Right region of all 2s

We use three pointers:

low: boundary between 0s and 1s
mid: current pointer
high: boundary between 1s and 2s

Approach (One-Pass, Constant Space)

Initialize three pointers:
- low = 0, mid = 0, high = n - 1
Traverse the array:
- If nums[mid] == 0: swap with nums[low], increment both low and mid
- If nums[mid] == 1: increment mid
- If nums[mid] == 2: swap with nums[high], decrement high only

Code (Java)

class Solution {
    public void sortColors(int[] arr) {
        int l = 0, h = arr.length - 1, i = 0;
        while (i <= h) {
            switch (arr[i]) {
                case 0: {
                    swap(arr, i, l);
                    l++;
                    i++;
                    break;
                }
                case 1: {
                    i++;
                    break;
                }
                case 2: {
                    swap(arr, i, h);
                    h--;
                    break;
                }
            }
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Time and Space Complexity

Metric	Value
Time	O(n)
Space	O(1)

Dry Run

Input: nums = [2,0,2,1,1,0]
Initial: low = 0, mid = 0, high = 5

Step	mid	nums[mid]	Action	Array	low	mid	high
1	0	2	Swap with nums[5]	[0,0,2,1,1,2]	0	0	4
2	0	0	Swap with nums[0], ++low	[0,0,2,1,1,2]	1	1	4
3	1	0	Swap with nums[1], ++low	[0,0,2,1,1,2]	2	2	4
4	2	2	Swap with nums[4]	[0,0,1,1,2,2]	2	2	3
5	2	1	Move mid	[0,0,1,1,2,2]	2	3	3
6	3	1	Move mid	[0,0,1,1,2,2]	2	4	3

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

Brute Force Approach (Counting Sort)

Steps:

Count the number of 0s, 1s, and 2s
Overwrite the array using these counts

Code:

class Solution {
    public void sortColors(int[] nums) {
        int[] count = new int[3];
        for (int num : nums) count[num]++;
        int index = 0;
        for (int i = 0; i < 3; i++) {
            while (count[i]-- > 0) {
                nums[index++] = i;
            }
        }
    }
}

Time: O(n)
Space: O(1) (count array is constant size)

Conclusion

The Dutch National Flag approach provides the optimal solution:

One traversal
Constant extra space
In-place operations

This is a classic partitioning and in-place sorting problem often asked in coding interviews.