This content originally appeared on DEV Community and was authored by sachin26
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] == redor0thenredCount++.
2. ifnums[i] == whiteor1thenwhiteCount++.
3. ifnums[i] == blueor2thenblueCount++.
step-3 again run a loop from i=0 to nums.length and then,
1. if
redCount != 0then,
nums[i] = red
redCount--.2. if
whiteCount !=0then,
nums[i] = white
whiteCount--.3. if
blueCount !=0thennums[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]=0orredthen,
swap(whitePointer,redPointer)
redPointer++
whitePointer++2. if
nums[whitePointer]=1orwhitethen,
whitePointer++3. if
nums[whitePointer]=2orbluethen,
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.
This content originally appeared on DEV Community and was authored by sachin26
sachin26 | Sciencx (2021-12-23T10:57:03+00:00) Striver’s SDE Sheet Journey – #5 Sort an array of 0s, 1s and 2s. Retrieved from https://www.scien.cx/2021/12/23/strivers-sde-sheet-journey-5-sort-an-array-of-0s-1s-and-2s/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.