NUHMAN.com

Introduction

LeetCode 75: Sort Colors is a classic algorithm problem often referred to as the Dutch National Flag problem, designed by Edsger Dijkstra. It involves sorting an array containing only three distinct elements (0, 1, and 2) in-place and in a single pass using constant space.

This is a frequent coding interview question that tests your ability to manipulate arrays efficiently and understand in-place partitioning.

Problem Statement

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 (0), white (1), and blue (2).

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

Example:

go

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

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

Approach: Dutch National Flag Algorithm

We use three pointers:

• low → to place the next 0
• mid → current element being evaluated
• high → to place the next 2

We iterate with mid and adjust the elements based on their value:

1. If the value is 0: swap it with low, increment both low and mid.
2. If the value is 1: just increment mid.
3. If the value is 2: swap it with high, decrement high (do not increment mid yet because the swapped value needs to be evaluated).

Go Implementation

go

func sortColors(nums []int) {
    low, mid := 0, 0
    high := len(nums) - 1

    for mid <= high {
        switch nums[mid] {
        case 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low++
            mid++
        case 1:
            mid++
        case 2:
            nums[mid], nums[high] = nums[high], nums[mid]
            high--
        }
    }
}

Explanation

• We initialize three pointers and iterate over the array once.
• The algorithm sorts the array in a single pass with O(n) time and O(1) space.
• Since we only deal with fixed values (0, 1, 2), this three-way partition is very effective.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

Where n is the number of elements in the input array.

Edge Cases

• Empty array: nothing to sort.
• Array with only one color: should remain unchanged.
• Already sorted array: should also remain unchanged.
• Large arrays with a random mix of 0s, 1s, and 2s.

Conclusion

LeetCode 75 is a fantastic example of how carefully managed pointers can result in an optimal solution with constant space and linear time. The Dutch National Flag algorithm is not only elegant but also widely applicable in partitioning problems.

Practicing this in Go provides deeper understanding of slice manipulation and in-place logic—skills that are invaluable in systems or performance-critical domains.