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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode.realtemirov.uz/problems/75.-sort-colors.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.