Leetcode 75: Sort Colors

1. Problem Statement (Simple Explanation)

You’re given an array nums of length n, where each element is:

• 0 → red

• 1 → white

• 2 → blue

You must sort the array in-place so that:

all 0s come first, then all 1s, then all 2s

No library sort is allowed.

Goal: one pass, O(1) extra space.

2. 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]

3. Approach 1 – Counting (Two Passes, O(1) extra)

Simple, but 2 passes:

1. Count how many 0s, 1s, and 2s.

2. Overwrite array:

• First count0 elements → 0

• Next count1 elements → 1

• Remaining count2 elements → 2

This is valid, O(n) time, O(1) space, but two passes.

4. Approach 2 – Dutch National Flag (One Pass, O(1) extra) – Recommended

We maintain three regions using pointers:

• low: boundary for the end of the 0-region.

• mid: current index scanning the array.

• high: boundary for the start of the 2-region.

Invariant during processing:

• nums[0..low-1] are all 0s.

• nums[low..mid-1] are all 1s.

• nums[high+1..n-1] are all 2s.

• nums[mid..high] are unknown (to process).

We scan with mid:

1. If nums[mid] == 0:

• Swap nums[low] and nums[mid].

• Increment both low and mid.

2. If nums[mid] == 1:

• Just mid++ (correct region already).

3. If nums[mid] == 2:

• Swap nums[mid] and nums[high].

• Decrement high.

• Do NOT increment mid in this case, because we need to process the new element at mid.

Stop when mid > high.

Pseudo-code (Dutch National Flag):

Complexity:

• Time: O(n) – each element moved at most once or twice.

• Space: O(1) – only a few pointers.

5. Java code

6. C code

7. C++ code

8. Python code

9. JavaScript code