Solving Arrays Questions | Sort 0,1,2 array | GeeksForGeeks | Nishant Chahar Ep-16
Solving Arrays Questions | Sort 0,1,2 array | GeeksForGeeks | Nishant Chahar Ep-16
In this video, we’ll are going to solve some more questions of the array. Arrays are really important because we are going to use them a lot in future topics. So make sure that you watch this lecture carefully.
Question link: https://practice.geeksforgeeks.org/pr…
Previous lecture: • Solving Arrays Questions | Find all p…
You can use my code NISHANT to get 15% Off on all GFG courses.
✨ Important Links ✨
- Don’t Click Here: https://bit.ly/3afmPha
- Telegram Link: https://t.me/codeIn10byNishant
- Github Repo Link: https://github.com/chaharnishant11/Co…
✨ Hashtags ✨
#NishantChahar #Microsoft #DSA #Recursion #FAANG #NSIT #NSUT #engineering #internship #college
✨tags ✨
Where to learn dp
where to learn graphs
where to learn dsa
how to start programming
how to start coding
where to learn trees
what is memoisation
what is tabulation
what are graphs
where to learn Operating systems
where to learn dbms
where to learn oops
where to learn computer networks
where to learn low level design
where to learn cs fundamentals
Sanchit jain
Gaurav sen
Gate smashers
Placement guide
How to start programming
where to learn cpp
where to learn python
where to learn javascript
where to learn java
Placement guide
Nishant Chahar Placement Guide
languages to learn
resources to learn data structures
Projects development
AR/VR
Blockchain Machine learning
Deep Learning
Software developer engineer ,
Side projects ,
Importance of side projects ,
Machine Learning Engineer,
How to become a machine learning engineer ,
Associate engineer
Data structures Algorithms
College Life, College, Memories
Fun Fests Chill Enjoy
IITD Mood indigo rendezvous IIT
NSUT Moksha DTU Engifest
Bits Bitsgoa
Namaste Javascript
Namaste Javascript Akshay Saini
Apna college
Apna college c++
apna college DSA
Where to learn dp
where to learn graphs
where to learn dsa
how to start programming
how to start coding
where to learn trees
what is memoisation
what is tabulation
what are graphs
where to learn programming
how to start coding
where to learn coding
where to learn DSA
resources to learn programming
how to crack amazon
how to crack placement
blockchain
what is blockchain
blockchain technology
blockchain technology explained
blockchain explained
blockchain technology in hindi
web development roadmap
roadmap to learn web development
android development roadmap
MERN stack roadmap
machine learning roadmap
roadmap to learn machine learning
roadmap for deep learning
roadmap for 2nd years
roadmap for opensource
roadmap for ios development
roadmap for deep learning
roadmap to learn DSA
Content
0 -> Hi guys I am Nishant Chahar. Welcome back to the channel code in 10
2.384 -> so inn today's video we gonna solve a question whose name is sort an array of zeros , ones and twos
6.769 -> so what is given in this question
8.228 -> you will be given an array
9.198 -> In which there are only 3 types of elements
10.288 -> 0, 1 and 2
11.749 -> okay
12.469 -> The elements will be of this type. They can be anything
14.085 -> now what you have to return
15.499 -> you have to return this in sorted order
17.127 -> first 0 should come, then all the ones should come, then all the twos should come
20.494 -> simple
21.154 -> so we gonna study three approaches
23.11 -> firstly, the easiest one
24.365 -> we applied sorting
26.337 -> okay
28.368 -> we applied sorting
29.249 -> we have studied two types of sorting on channel. merge and quick
34.031 -> sorting has many other types
36.635 -> but the internal sort function
39.423 -> if you will use that
41.07 -> that solves in nlogn time complexity
44.633 -> okay, it solves in this time complexity
48.301 -> so we will consider that the time complexity of first solution is nlogn
52.646 -> so the nlogn time complexity is a little bit less good than n
57.918 -> nlogn take more time than n
60.392 -> because if you multiply anything with x
63.021 -> so its value increases
64.355 -> right, if you will do 5 into 2, then it will be 10
66.875 -> if you will multiply with any x
68.783 -> so that thing will be increasing
69.893 -> so here this thing
71.749 -> nlogn is good than n square
74.666 -> okay
75.243 -> but it is bad than n
77.462 -> so we have to reach in this time complexity
79.735 -> so we will have to optimize a little bit
80.964 -> okay
81.852 -> so there is one more way of sorting
83.805 -> that we call count sort
85.559 -> we call it count sort. What is the meaning of count sort
88.358 -> we count elements
89.783 -> we traversed in array one time
92.478 -> in complete
94.038 -> and we stored a frequency map type
98.741 -> that how many times 0 is coming, how many times 1 is coming, how many times 2 is coming
100.488 -> how many times 3 is coming
101.354 -> in this way we stored everything
103.177 -> and after that what we did
104.551 -> we applied one more loop
105.286 -> then we kept on seeing that 0 came this much times
107.269 -> we added 0 in loop this much time
108.577 -> we went
110.612 -> we checked how many times 0 came
111.842 -> we run that much time in loop
113.496 -> and added 0,0,0,0 in array
114.796 -> then 1, then 2
115.661 -> doing in this way
116.461 -> we add that
117.963 -> so let me show you by solving it
119.153 -> lets take the example that is given
120.571 -> here we are given this array
121.989 -> in this we just have to count zeros, ones and twos
124.686 -> what we will do? we will go and count
126.051 -> how many times 0 is coming
127.383 -> it is coming one time
128.236 -> then 2 is coming one time
130.473 -> then one is coming one time
131.773 -> then two came again, so we did this as two
133.593 -> then 0 came again , so we did this as 2
135.157 -> so we got that 0 is coming 2 times, 1 is coming one time and 2 is coming two times
138.912 -> we will run a loop again
140.426 -> okay
141.555 -> we ran loop as much times as 0 is coming
144.534 -> and added 0 in that
145.379 -> then how many times 1 is coming, did that much times
146.781 -> how many times 2 is coming , did that much times
148.251 -> you will see that we got this sorted
149.939 -> got is sorted?
152.111 -> simple and easy
153.401 -> what are we doing in it
155.264 -> we are running the loop two times in it
157.176 -> we are running it two times
158.617 -> so its time complexity is 2 into n
161.428 -> order of 2 into n
164.689 -> but when it is constant
166.767 -> so we consider it order of n generally
171.024 -> We gonna study all of this in time complexity very soon
174.653 -> after one or two topics, we will study time complexity
178.182 -> then you will understand all these terms that must be currently seeming to you as aliens
181.767 -> don't worry
182.731 -> now what we have to do
183.803 -> there is one more algorithm
185.459 -> okay
187.313 -> there is a very famous algorithm
189.082 -> Dutch Flag algorithm
192.554 -> there is an algorithm Dutch Flag
194.799 -> okay
195.771 -> what we do in that
196.945 -> we will solve this question by using that
198.711 -> if you listened it first time, then no need to worry
200.862 -> we will solve
202.307 -> I will also make you learn algorithm
203.378 -> after that we will also solve this question too
204.779 -> okay
205.577 -> first let me tell you how its name came
207.629 -> Dutch Flag looks something like this
208.998 -> Dutch Flag looks something like this
211.6 -> There are three parts in that
212.413 -> okay
213.272 -> so to do three parts, we make this like this
215.954 -> because there will be 3 parts here also
217.155 -> one is 0's part
217.838 -> one is 1's part and one is 2's part
219.015 -> so as we are given an array
222.054 -> 0 0 1 2 1 3
225.161 -> 1 1 1 2 2 0
228.884 -> we are given an array
230.394 -> so what happens in it
231.637 -> there exists three pointers in it
232.641 -> one is low, one is mid, and one is high
236.481 -> okay
238.183 -> now whatever comes in it after sorting
241.141 -> sort happens from where to where
242.868 -> in sort we say, there will be zeros from 0 to low -1
248.192 -> okay
249.591 -> after that from low
252.593 -> to high
254.742 -> from low to high, you will have ones
259.306 -> and your twos will be from high+1 to n-1
264.571 -> How they will be there?
266.211 -> lets tell
267.266 -> what is the work of mid
268.392 -> the work of mid here is to traverse the array
271.095 -> we traverse the array
272.669 -> by using mid
273.653 -> and we do this until the value of mid is less than high
278.173 -> we keep traversing it till then
280.522 -> now what happens in this algorithm, lets understand that
283.003 -> mid and low exists in starting
287.373 -> and high in the end
288.946 -> okay
290.084 -> so low is placed on 0th index
292.422 -> mid is kept on 0
293.879 -> and high is placed in the end
295.454 -> it remains at n-1
297.049 -> okay
298.002 -> it remains at n-1
299.904 -> now what happens after this , we start running the algorithm
302.36 -> so what we do
303.356 -> whenever we encounter 0
305.86 -> as soon as encountering 0
307.242 -> we just swap that with low
309.716 -> whatever is present at mid
310.669 -> we swap mid with low
311.943 -> okay
312.821 -> and we do low ++
314.028 -> and we also do mid++
315.276 -> okay
316.214 -> and after this
317.298 -> when we get 1
319.246 -> we just increase mid ahead
320.552 -> and when we get 2
322.039 -> we swap mid with high
323.97 -> and we do high--
325.855 -> and mid ++
327.269 -> right
328.159 -> okay
328.989 -> when we get two, then what we do
331.232 -> we do nothing to mid
333.934 -> and we swap mid with high
335.489 -> and we just do high --
337.89 -> so we do this
339.211 -> This is our complete algorithm
340.378 -> okay
341.376 -> This is some basic of algo
343.312 -> lets start this coding quickly
344.957 -> I will explain you while coding
346.547 -> after that we will try to dry run it
347.998 -> so we are given array and n here
350.16 -> what we will so, we will make a row
351.694 -> It will be 0. We will make a mid
356.497 -> whatever will be 0
358.547 -> and we will make a high
361.072 -> that will be n-1
362.578 -> okay
363.392 -> now what we will do
364.426 -> we will apply while loop
365.266 -> what we will do in while loop
366.472 -> until the value of mid, is less than high
368.899 -> This loop will keep running until then
371.165 -> okay
372.249 -> inside it we will check first
373.398 -> if in array
375.603 -> if the value of mid
376.882 -> is equals to 0
378.082 -> so what we will do
381.395 -> we will just swap
383.125 ->
388.886 -> so what we will do here
389.898 -> we will just do swap
390.936 -> arr of mid, arr of low
397.476 -> we will do mid ++
399.936 -> and we will also do low ++
404.607 -> else if the value of arr of mid
410.76 -> becomes 1
412.356 -> so we just have to do mid ++
414.522 -> and in last , in else case it is just left
416.963 -> that if it becomes 2
418.202 -> In that , we first have to swap mid
421.164 -> with high
423.785 -> okay
425.777 -> and we have to do high --
427.779 -> that's it
430.028 -> our work is done
431.218 -> this will be sorted
432.368 -> and print
433.379 -> so lets run it quickly
435.479 -> okay sorry, it is not arr , it is a
439.386 -> no problem , lets do it arr
440.683 -> okay
443.21 -> 0 0 1 2 2
444.315 -> 0 0 1 2 2
445.402 -> lets submit
446.145 -> so we have done a mistake here
448.142 -> this should be less than equals to high
450.709 -> because we will check till end
451.647 -> that going until high
453.453 -> and here our all the test cases have been passed
457.325 -> right
458.409 -> now there are 1-2 things in it
460.113 -> one is why we didn't do mid ++ here
462.9 -> why we did high -- here
466.251 -> like if it is here, so we did both
467.32 -> so what happens when we swap this
470.182 -> if we did this position ahead
471.903 -> so there we do not know what new element has come on the mid
474.825 -> and we will have to check later that what element is coming in the mid
477.458 -> okay
478.724 -> because we can have to swap mid somewhere
481.172 -> that is why we do not do mid ++
482.865 -> with this
483.717 -> it can happen , at mid, 0 was present in the last
486.579 -> at high
487.758 -> and here 2 was present
489.493 -> now here 0 came
490.395 -> right
491.344 -> now we will also have to swap this with low
493.464 -> if we will not swap this with low, so 0 will be left in between, in complete 1's part
498.126 -> so here problem will come
499.271 -> lets try to dry run it quickly now
501.336 -> we are given an array
502.298 -> what we did, we started from here
503.621 -> our low's value is 0
505.726 -> our high's value is n-1
509.345 -> what is n? it is 10
510.718 -> so it became 9
511.533 -> and our mid's value is also 0
515.773 -> we started that mid is less than 9, yes it is
518.665 -> what is present at array mid? 0 is present at array mid
521.032 -> so we will do nothing
521.988 -> we will swap these mutually
523.854 -> if we will swap, then it will stay here, nothing will be changed
525.932 -> and we will increase the value of both of these two
527.846 -> okay
528.758 -> we will go back in the loop
529.57 -> we will check again, if the value of mid is less than high
532.213 -> now what is present at mid 1? 0 is present
534.271 -> we will do nothing again
535.201 -> we will do both as 2
536.104 -> okay
537.629 -> we will check again
538.616 -> 2 is less than equal to high. Of course
540.423 -> 2 is less than equals to
541.336 -> we will go again and see here what is present at 2. one is present at 2
544.14 -> so we will just ++ it
545.846 -> we will do nothing
546.817 -> our mid reached here
547.811 -> at next we will check
548.682 -> here we will get 2 again
550.552 -> if we will get 2 then what we will do
552.274 -> now our array is this
553.805 -> so what we will do
556.532 -> we will do this as 0 here
557.68 -> here we will do it 2 after removing it
560.059 -> and our mid is here, we will bring high here
562.147 -> and our low is currently here
564.489 -> right
565.181 -> this is your low, this is your mid
566.919 -> this is your high
568.724 -> now I was talking about this condition only
570.669 -> that if we also do mid ++ here
572.925 -> so our 1 would have left there
573.721 -> and this 0 would have never be swapped
575.319 -> right
576.352 -> so we will go again
577.503 -> here mid ++ didn't happen
579.21 -> this became 8
580.062 -> we checked again
581.888 -> if 3 is less than equals to 8? Yes of course. So we will check what is present on it, 0 is present
584.995 -> so what we did
586.197 -> we swapped this
587.23 -> 1 came
588.491 -> okay
589.592 -> we brought mid here
590.379 -> and low here
591.485 -> okay
592.707 -> now we checked again
594.193 -> this will keep on increasing
595.793 -> it will come till here
596.623 -> it will come till here
597.769 -> and after coming till here, next it will go till 2
600.613 -> it will check on 2 what is present
602.104 -> it will swap these 2
603.41 -> here 1 will come
604.155 -> here 2 will come
605.3 -> then it will go ahead
607.285 -> it will not be able to go ahead of it
608.62 -> because the value of high will be equal to mid
611.942 -> and no need to go ahead of it
613.677 -> and our complete array will be sorted
616.481 -> se 0 0 0 1 1 1 1 2 2 2 2 2
619.711 -> and our array has been sorted
621.187 -> it is very simple
622.947 -> but yes this is different algorithm
624.566 -> generally people get confused in it
626.398 -> People get confused in this thing generally
627.727 -> that we have done mid ++ at every place
630.221 -> we have done mid++ everywhere
632.261 -> why we didn't do here?
633.086 -> and why we did this greater than equal to
636.37 -> why not only less than
637.245 -> if we would do less than, then here also our one variable would have left
640.309 -> one more index would have left
641.735 -> where we would not be checking after going on mid
643.45 -> that is why we do this less than equal to
645.152 -> So this was it for the video
647.74 -> I hope you have understood the video
649.025 -> I hope you have understood the concept
650.193 -> Thank you so much for watching this video
651.582 -> lets meet in another video. Till then bye
Source: https://www.youtube.com/watch?v=R6HoR6NyMOA