75. Sort Colors

🟧 Medium

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 color red, white, and blue, respectively.

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

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

• nums[i] is either 0, 1, or 2.

Solution

My Solution (Counting Sort)

func sortColors(nums []int) {
    zero, one, two := 0, 0, 0
    for _, v := range nums {
        if v == 0 {
            zero++
        } else if v == 1 {
            one++
        } else {
            two++
        }
    }

    for i := range nums {
        if i < zero {
            nums[i] = 0
        } else if i < zero+one {
            nums[i] = 1
        } else {
            nums[i] = 2
        }
    }
}

Optimal Solution (Dutch National Flag Algorithm)

func sortColors(nums []int) {
    // Three pointers for three sections
    left, curr, right := 0, 0, len(nums)-1
    
    // Process until current pointer crosses right pointer
    for curr <= right {
        switch nums[curr] {
        case 0: // Red
            // Swap with left section and advance both pointers
            nums[left], nums[curr] = nums[curr], nums[left]
            left++
            curr++
        case 1: // White
            // Already in correct position
            curr++
        case 2: // Blue
            // Swap with right section and only move right pointer
            nums[curr], nums[right] = nums[right], nums[curr]
            right--
        }
    }
}

Approach

This solution uses the Dutch National Flag algorithm (by Edsger Dijkstra):

1. Key Insight:

   • Array can be divided into four sections:

     • [0, left): All 0s (red)

     • [left, curr): All 1s (white)

     • [curr, right]: Unknown elements

     • (right, n-1]: All 2s (blue)

2. Implementation Strategy:

   • Use three pointers: left, curr, and right

   • Process elements at curr pointer

   • Maintain invariant sections through swaps

3. Processing Rules:

   • 0: Swap with left section

   • 1: Keep in place

   • 2: Swap with right section

Complexity Analysis

Time Complexity: O(n)

• Single pass through the array

• Each element processed at most twice

• All operations are O(1)

• No extra passes needed

Space Complexity: O(1)

• Only constant extra space used:

  • Three pointers (left, curr, right)

  • One temporary variable for swaps

  • No additional data structures

Why it works

• Partition Properties:

  • Elements < curr are properly sorted

  • Elements > right are properly sorted

  • Unknown elements between curr and right

  • Invariants maintained by pointer movements

• Optimization Details:

  • In-place sorting

  • Single pass through array

  • Minimal swaps needed

  • Stable within color groups

• Key Improvements over Original:

  • No counting needed

  • No second pass required

  • True in-place algorithm

  • Better cache performance

• Edge Cases Handled:

  • All same colors

  • Already sorted array

  • Reverse sorted array

  • Small arrays (n < 3)

result

Leetcode: link