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
or0
thenredCount++
.
2. ifnums[i] == white
or1
thenwhiteCount++
.
3. ifnums[i] == blue
or2
thenblueCount++
.
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
thennums[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
orred
then,
swap(whitePointer,redPointer)
redPointer++
whitePointer++
2. if
nums[whitePointer]
=1
orwhite
then,
whitePointer++
3. if
nums[whitePointer]
=2
orblue
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)