> For the complete documentation index, see [llms.txt](https://leetcode.realtemirov.uz/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode.realtemirov.uz/problems/75.-sort-colors.md).

# 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)

```go
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)

```go
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](/files/kAVWYGPiPUTjgV9YcJc0)

Leetcode: [link](https://leetcode.com/problems/sort-colors/description/)