Solving the LeetCode "Sort Colors" Problem in Go

Difficulty: Medium | Tags: Array, Two Pointers, Sorting

Introduction

The "Sort Colors" problem requires sorting an array of integers representing colors (0 for red, 1 for white, and 2 for blue) in-place without using a library sort function. This problem is a classic example of the Dutch National Flag algorithm.

Problem Analysis

Given an array of integers where each element is 0, 1, or 2, the task is to sort the array so that all 0s come first, followed by 1s, and then 2s. The challenge is to achieve this in a single pass with constant space complexity.

Solution Approach

The Dutch National Flag algorithm is an efficient way to solve this problem. It involves maintaining three pointers: low, mid, and high. The low pointer tracks the boundary of 0s, the high pointer tracks the boundary of 2s, and the mid pointer traverses the array to classify elements.

Go Implementation

func sortColors(nums []int) {
    low, mid, high := 0, 0, 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--
        }
    }
}

Complexity Analysis

The algorithm runs in O(n) time complexity since it processes each element exactly once. The space complexity is O(1) as it uses only a constant amount of additional space.

Testing and Examples

Test cases:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Input: [2,0,1]
Output: [0,1,2]
Edge Case: [1,1,1]
Output: [1,1,1]

Best Practices and Tips

Key takeaways include understanding the Dutch National Flag algorithm and its efficiency for such partitioning problems. Always validate edge cases, such as arrays with all elements of the same value or empty arrays.