Algorithm Day99 - Sort Colors

Posted on In , , Views:

🧩 Problem

LeetCode 75 - Sort Colors
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the colors red, white, and blue respectively.

You must solve this problem without using the library’s sort function.

Example:

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

💡 Idea

This is a Dutch National Flag problem, invented by Edsger Dijkstra.
We use three pointers to partition the array into three regions:

  • 0 ... low-1: all 0s
  • low ... mid-1: all 1s
  • high+1 ... end: all 2s

We iterate using mid:

  • If nums[mid] == 0: swap with low, increment both low and mid
  • If nums[mid] == 1: just increment mid
  • If nums[mid] == 2: swap with high, decrement high

This ensures a one-pass, in-place sorting solution.

💻 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;
        while (mid <= high) {
            if (nums[mid] == 0) {
                swap(nums, low++, mid++);
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                swap(nums, mid, high--);
            }
        }
    }

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

🧠 Complexity

  • Time: O(n) — Single pass through the array
  • Space: O(1) — In-place swaps only

🏁 Summary

This problem is a perfect example of in-place array manipulation using multiple pointers.
The Dutch National Flag algorithm is elegant, efficient, and a must-know for array partitioning problems.