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.

Problem Statement:-

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

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

##
__Solution 1__

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

##
__Solution 2__

*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

```
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;
}
}
}
}
```

##
__Solution 3__

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.

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.

## Top comments (0)