# Sort Colors
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sort-colors)
Canonical: https://scaleengineer.com/dsa/problems/sort-colors
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Docusign](https://scaleengineer.com/companies/docusign), [Flipkart](https://scaleengineer.com/companies/flipkart), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [Samsung](https://scaleengineer.com/companies/samsung), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [tcs](https://scaleengineer.com/companies/tcs), [Zopsmart](https://scaleengineer.com/companies/zopsmart), [Optum](https://scaleengineer.com/companies/optum), [Salesforce](https://scaleengineer.com/companies/salesforce), [Autodesk](https://scaleengineer.com/companies/autodesk), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Swiggy](https://scaleengineer.com/companies/swiggy), [PhonePe](https://scaleengineer.com/companies/phonepe), [Sprinklr](https://scaleengineer.com/companies/sprinklr), [Pocket Gems](https://scaleengineer.com/companies/pocket-gems), [Arcesium](https://scaleengineer.com/companies/arcesium), [Groww](https://scaleengineer.com/companies/groww), [Target](https://scaleengineer.com/companies/target)
---
## Problem
Given an array `nums` with `n` objects colored red, white, or blue, sort them **[in-place](https://en.wikipedia.org/wiki/In-place%5Falgorithm)** 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`.

**Follow up:** Could you come up with a one-pass algorithm using only constant extra space?

# Approaches
## Brute Force using Comparison Sort
The most straightforward, albeit inefficient, way to solve this problem is to use a standard comparison-based sorting algorithm. Since the problem prohibits using the library's built-in sort function, we can implement a simple one like Bubble Sort. This approach repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The passes through the list are repeated until the list is sorted.
**Time:** O(n^2) · **Space:** O(1)
**Pros:** Easy to understand if familiar with basic sorting algorithms.; It's an in-place sorting algorithm, so it uses constant extra space.
**Cons:** Very inefficient compared to other methods.; Does not leverage the specific properties of the input (only three distinct values).; Has a time complexity of O(n^2), which is slow for larger inputs.
### Explanation
This approach treats the problem as a generic sorting problem. We can implement an algorithm like Bubble Sort, which works by repeatedly swapping adjacent elements if they are in the wrong order. We would need two nested loops. The outer loop decreases the effective size of the array to be sorted in each iteration, as the largest elements 'bubble up' to the end. The inner loop performs the actual comparisons and swaps.

For an input like `[2,0,2,1,1,0]`, the algorithm would perform multiple passes, gradually moving the 0s to the left and 2s to the right, until the array is fully sorted as `[0,0,1,1,2,2]`.

```java
class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    // Swap nums[j] and nums[j+1]
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                    swapped = true;
                }
            }
            // If no two elements were swapped by inner loop, then break
            if (!swapped) {
                break;
            }
        }
    }
}
```
### Algorithm
1.  Implement a standard sorting algorithm like Bubble Sort.
2.  Use nested loops to iterate through the array.
3.  The outer loop runs from `i = 0` to `n-2`.
4.  The inner loop runs from `j = 0` to `n-i-2`.
5.  Inside the inner loop, compare `nums[j]` and `nums[j+1]`.
6.  If `nums[j] > nums[j+1]`, swap the two elements.
7.  After the loops complete, the array will be sorted.

## Counting Sort (Two-Pass)
A more efficient approach is to use a variation of Counting Sort. Since we know the range of values is limited to 0, 1, and 2, we can count the occurrences of each color in a first pass. Then, in a second pass, we can overwrite the original array with the correct number of 0s, followed by 1s, and then 2s. This is a two-pass algorithm.
**Time:** O(n) · **Space:** O(1)
**Pros:** Linear time complexity O(n), which is a significant improvement over O(n^2).; Simple logic to implement and understand.; Uses constant extra space (O(1)) for the counters.
**Cons:** Requires two passes over the array, which is less optimal than a single-pass solution.; It's not a true in-place sort as it overwrites the array based on counts rather than swapping elements.
### Explanation
This method involves two distinct steps. First, we iterate through the entire array to count how many 0s, 1s, and 2s are present. We can use three integer variables, say `count0`, `count1`, and `count2`, for this purpose. 

After counting, we know the exact composition of the sorted array. For example, if `count0=2`, `count1=2`, and `count2=2`, the sorted array must be `[0,0,1,1,2,2]`. The second step is to modify the input array in-place. We use a pointer, starting at index 0, and fill the array first with `count0` zeros, then with `count1` ones, and finally with `count2` twos.

```java
class Solution {
    public void sortColors(int[] nums) {
        int count0 = 0, count1 = 0, count2 = 0;
        for (int num : nums) {
            if (num == 0) {
                count0++;
            } else if (num == 1) {
                count1++;
            } else {
                count2++;
            }
        }

        int i = 0;
        // Overwrite array with count0 zeros
        for (int j = 0; j < count0; j++) {
            nums[i++] = 0;
        }
        // Overwrite array with count1 ones
        for (int j = 0; j < count1; j++) {
            nums[i++] = 1;
        }
        // Overwrite array with count2 twos
        for (int j = 0; j < count2; j++) {
            nums[i++] = 2;
        }
    }
}
```
### Algorithm
1.  Initialize three counters: `count0 = 0`, `count1 = 0`, `count2 = 0`.
2.  **First Pass:** Iterate through the `nums` array from start to end.
3.  For each element, increment the corresponding counter. If `num == 0`, increment `count0`, etc.
4.  **Second Pass:** Overwrite the `nums` array.
5.  Initialize a pointer `i = 0`.
6.  Fill the first `count0` elements of `nums` with `0`.
7.  Fill the next `count1` elements of `nums` with `1`.
8.  Fill the final `count2` elements of `nums` with `2`.

## Dutch National Flag Algorithm (One-Pass)
The optimal solution is a one-pass, in-place algorithm often referred to as the Dutch National Flag problem. This approach uses three pointers (`low`, `mid`, and `high`) to partition the array into three sections: a section for 0s at the beginning, a section for 2s at the end, and a section for 1s in the middle. We iterate through the array with the `mid` pointer, swapping elements into their correct partitions.
**Time:** O(n) · **Space:** O(1)
**Pros:** Optimal time complexity of O(n).; Optimal space complexity of O(1).; Achieves the sort in a single pass over the data.; Directly addresses the follow-up question.
**Cons:** The logic, especially the pointer movements, can be slightly tricky to get right on the first try.
### Explanation
This elegant one-pass solution partitions the array in-place. We maintain three pointers:
- `low`: Marks the boundary of the `0`'s section. All elements before `low` are `0`.
- `high`: Marks the boundary of the `2`'s section. All elements after `high` are `2`.
- `mid`: Is the current element being processed.

We iterate with `mid` from the beginning of the array. 
- If `nums[mid]` is `0`, it belongs to the `low` section. We swap it with `nums[low]` and increment both `low` and `mid`.
- If `nums[mid]` is `1`, it's in the correct place for now, so we just move to the next element by incrementing `mid`.
- If `nums[mid]` is `2`, it belongs to the `high` section. We swap it with `nums[high]` and decrement `high`. We do *not* increment `mid` in this case, because the element we just swapped into the `mid` position from the `high` end is unprocessed and needs to be checked.

The loop continues until `mid` crosses `high`, at which point the array is fully sorted.

```java
class Solution {
    public void sortColors(int[] nums) {
        int low = 0;
        int mid = 0;
        int high = nums.length - 1;

        while (mid <= high) {
            switch (nums[mid]) {
                case 0: {
                    int temp = nums[low];
                    nums[low] = nums[mid];
                    nums[mid] = temp;
                    low++;
                    mid++;
                    break;
                }
                case 1: {
                    mid++;
                    break;
                }
                case 2: {
                    int temp = nums[mid];
                    nums[mid] = nums[high];
                    nums[high] = temp;
                    high--;
                    break;
                }
            }
        }
    }
}
```
### Algorithm
1.  Initialize three pointers: `low = 0`, `mid = 0`, and `high = n - 1`.
2.  The region `0` to `low-1` contains `0`s.
3.  The region `low` to `mid-1` contains `1`s.
4.  The region `high+1` to `n-1` contains `2`s.
5.  The region `mid` to `high` is the unsorted part.
6.  Iterate while `mid <= high`:
    *   If `nums[mid] == 0`: Swap `nums[low]` with `nums[mid]`. Increment both `low` and `mid`.
    *   If `nums[mid] == 1`: The element is in its correct partition. Increment `mid`.
    *   If `nums[mid] == 2`: Swap `nums[mid]` with `nums[high]`. Decrement `high`. Do not increment `mid` as the new `nums[mid]` needs to be processed.

# Solutions
### CSharp

```csharp
public class Solution {
    public void SortColors(int[] nums) {
        int i = -1, j = nums.Length, k = 0;
        while (k < j) {
            if (nums[k] == 0) {
                swap(nums, ++i, k++);
            } else if (nums[k] == 2) {
                swap(nums, --j, k);
            } else {
                ++k;
            }
        }
    }
    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}
```

### Java

```java
class Solution {
public
  void sortColors(int[] nums) {
    int i = -1, j = nums.length, k = 0;
    while (k < j) {
      if (nums[k] == 0) {
        swap(nums, ++i, k++);
      } else if (nums[k] == 2) {
        swap(nums, --j, k);
      } else {
        ++k;
      }
    }
  }
private
  void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
  }
}

```

### CPP

```cpp
class Solution {
public:
  void sortColors(vector<int> &nums) {
    int i = -1, j = nums.size(), k = 0;
    while (k < j) {
      if (nums[k] == 0) {
        swap(nums[++i], nums[k++]);
      } else if (nums[k] == 2) {
        swap(nums[--j], nums[k]);
      } else {
        ++k;
      }
    }
  }
};

```

### Python

```python
class Solution : def sortColors ( self , nums : List [ int ]) -> None : i , j , k = - 1 , len ( nums ), 0 while k < j : if nums [ k ] == 0 : i += 1 nums [ i ], nums [ k ] = nums [ k ], nums [ i ] k += 1 elif nums [ k ] == 2 : j -= 1 nums [ j ], nums [ k ] = nums [ k ], nums [ j ] else : k += 1
```