Striver's SDE Sheet Journey - #5 Sort an array of 0s, 1s and 2s
Tags: beginners, java, programming, computerscience
Published: 2021-12-23 10:57:03


Hi👋Devs,

I hope you getting something from the series, now we came to the 5th problem, let's solve the problem without wasting any time.


> **<u>Problem Statement</u> :-**

_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._

This is a **Dutch national flag problem** was proposed by [Diskstra](https://en.wikipedia.org/wiki/Dutch_national_flag_problem#:~:text=The-,Dutch%20national%20flag%20problem,-%5B1%5D%20is%20a).

**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]
```

##  <u>Solution 1</u>
_we can easily solve this problem by using any sorting algorithm. the sorting algorithm will sort the array `nums` in ascending order and that would be our expected output._

##  <u>Solution 2</u>
_the array `nums` only contains the three unique values 0's,1's,2's. so what we need to do is just create three variables that store the frequency of the three unique values and after that overwrite the array based on the frequency of the values._

lets understand this approach step by step.

**step-1** initialize three variable.
 `redCount = 0`,
 `whiteCount = 0`,
 `blueCount = 0`

**step-2** run a loop from `i=0` to `nums.length` and then,
> **1.** if `nums[i] == red` or `0` then `redCount++`.
> **2.** if `nums[i] == white` or `1` then `whiteCount++`.
> **3.** if `nums[i] == blue` or `2` then `blueCount++`.

**step-3** again run a loop from `i=0` to `nums.length` and then,
> **1.** if `redCount != 0` then,
 `nums[i] = red`
 `redCount--`.

> **2.** if `whiteCount !=0` then,
 `nums[i] = white`
 `whiteCount--`.

> **3.** if `blueCount !=0` then `nums[i] = blue`.

**step-4** end.

> Java

```java
class Solution {
    public void sortColors(int[] nums) {
       
        final int red=0, white=1, blue=2;
        int redCount = 0, whiteCount = 0, blueCount = 0;
        
        for(int i=0; i<nums.length;i++){
            
            int color = nums[i];
            switch(color){
                case red:
                    redCount++;
                    break;
                    
                case white:
                    whiteCount++;
                    break;
                    
                case blue:
                    blueCount++;
                    break;
            }
        }
        
        for(int i=0; i<nums.length; i++){
            
            if(redCount != 0){
                nums[i] = 0;
                redCount--;
            }
            else if(whiteCount != 0){
                 nums[i] = 1;
                whiteCount--;
            }else{
                nums[i] = 2;
            }
        }
    }
}
```

##  <u>Solution 3</u>
let's discuss the main algorithm that is **three-way partitioning** was proposed by Dijkstra himself.

_in this algo we are classifying the `nums` array into 3 groups by using three pointers._

**step-1** initialize three pointers `redPointer = 0`, `whitePointer = 0`, `bluePointer = nums.length -1`.

**step-2** run a loop from `whitePointer` to `bluePointer` and then,
> **1.** if `nums[whitePointer]` = `0` or `red` then,
 `swap(whitePointer,redPointer)`
 `redPointer++`
 `whitePointer++`

> **2.** if `nums[whitePointer]` = `1` or `white` then,
 `whitePointer++`

> **3.** if `nums[whitePointer]` = `2` or `blue` then,
 `swap(whitePointer,bluePointer)`
 `bluePointer--`

**step-4** end.

look at this picture for a better understanding.


![Sort an array of 0s, 1s and 2s](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ex18o3oghvml2pawkcb8.png)


> Java

```java
class Solution {
    public void sortColors(int[] nums) {
        
      final int red = 0, white = 1, blue = 2;
      int redPointer = 0, whitePointer = 0, bluePointer = nums.length -1;
        
        while(whitePointer <= bluePointer){
            
            int color = nums[whitePointer];
            
            switch(color){
                    
                case red:
                    swap(nums,whitePointer,redPointer);
                    redPointer++;
                    whitePointer++;
                    break;
                    
                case white:
                    whitePointer++;
                    break;
                    
                case blue:
                    swap(nums,whitePointer,bluePointer);
                    bluePointer--;
                    break;
            }
        }
    }
    
    private void swap(int[] arr,int firstIndex,int secondIndex){
        int temp = arr[firstIndex];
        arr[firstIndex] = arr[secondIndex];
        arr[secondIndex] = temp;
    }
}
```

> **_Time Complexity⏱️_**

loop running from whitePointer to bluePointer, then
Time Complexity: **O(n)**



> **_Space Complexity⛰️_**

the algo is not using any extra space then ,
Space Complexity: **O(1)**


Thank you for reading this article I tried to stay clean & simple in my explanations and if you like this article then like and share it with your devs friend.