# Striver's SDE Sheet Journey - #5 Sort an array of 0s, 1s and 2s

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)