# LC-75 Sort Colors(Dutch Flag Problem)

You are given an array `nums` with `n` objects colored red, white, or blue, sort them [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm) 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.

## Brute Force Solution: -

Approach is straight-forward. Since the array consists of only **0s,1s** and **2s,** we can count the frequency of them and refill the array with **0s,1s** and **2s** respectively.

```plaintext
zc = 0, oc = 0, tc = 0
n = nums.size()

for int i = 0 to i < n and i++
    if(nums[i] == 0)
        zc++;
    else if(nums[i] == 1)
        oc++;
    else
        tc++;

for int i = 0 to i + zc and i++
    nums[i] = 0

for int i = zc to i < zc + oc and i++
    nums[i] = 1

for int i = zc + oc to i < zc + oc + tc and i++
    nums[i] = 2
```

*   **Time Complexity: O(n)**
    
*   **Space Complexity : O(1)**
    

## Optimal Solution: -

Although the above solution is fine in terms of time and space complexity, but as you can see, we are performing multiple passes. Instead, we can solve this question in a single pass(**In-Place)** which is the desired solution

![](https://cdn.hashnode.com/uploads/covers/67f507f5a7ff4d4a94882083/a3a67567-c90a-41ab-ba0d-4a24b77c077f.png align="center")

*   We will maintain 3 regions and we name them as **0-region, 1-region , 2-region.** These regions are imaginary just for the sake of solving the problem.
    
*   The zone **mid to high** is given to us as question.
    
*   Approach is like initialise **low = 0, mid = 0 and high = n - 1**
    
*   If nums\[mid\] == 0, simply swap **nums\[mid\] and nums\[low\]**. Now since **low to mid - 1** is **1s** zone, we have to increment both **low and mid**. This will be clear if you trace this on paper by drawing the above zones.
    
*   If nums\[mid\] == 1, simply increment mid.
    
*   If nums\[mid\] == 2, swap **nums\[mid\] and nums\[high\]** and decrement high.
    

```plaintext
int low = 0, mid = 0, high = n - 1

while(mid <= high){
    if(nums[mid] == 0){
        swap(nums[mid],nums[low]);
        low++;
        mid++;
    }
    
    else if(nums[mid] == 1)
        mid++;
    
    else{
        swap(nums[mid],nums[high]);
        high--;
    }
}
```

*   **Time Complexity: O(n)**
    
*   **Space Complexity : O(1)**