Sort Colors - Quicksort Partition - Leetcode 75 - Python

[@ihashib]

When I started programming, I used to think how the heck I am gonna learn solving problems if I can't solve them on my own but I am amazed that I can now go close to the solve before getting stuck on edge cases and looking for the solve! Thank you!

[@jhs1430]

Thank you so much for the video! In case someone wonders why use i -= 1 followed by i +=1, it is a little bit weird to me, but it works. In fact, if we simply delete lines 21 and 22, and add i += 1 in the nums[i] == 0 case, there will be an infinite loop. To solve the problem, add "else: i += 1" (to handle nums[i] == 1 case).

[@alexisacosta6758]

Thanks for this comment. Saved me so much time.

[@frankl9634]

Your videos are by far the best explanations I have seen on KZbin so far. Concise and straightforward. Thank you very much! Keep it coming. 😀

[@NeetCode]

Thanks! Happy they are helpful!

[@peterkim1867]

Just wanted to say that you've been a huge help as the way you approach problems is how a normal-person can approach and potentially solve problems. This video and explanation is top notch in explaining partitioning arrays, but it leaves out the rest of quicksort. I would guess if there were more than 3 possible options then we would go through the rest of quicksort. Please feel free to use quicksort on a future video with more possible options!

[@expansivegymnast1020]

Another banger. You're gonna help me get employed in the tech industry.

[@rishikaverma9846]

Cannot imagine solving leetcode without your solutions

[@hdtlab]

Omg. First time heard of “bucket sort” and instantly got a use case in reality. Very nice video ❤

[@tonypaus13]

Thanks. This seemed so difficult, but after spending about 30 minutes on this problem with Neetcode I could understand why that I pointer wasn't incremented at 2.

[@shenzheng2116]

Excellent explanation! Your channel deserves 1 billion subscribers :)

[@saigouthamipriyankaraparth5872]

Hello! Your channel is the best for Python developers learning to leetcode. Thanks a lot for those crystal clear explanations. I have a question, why did you not use the pythonic way of swapping and used an extra function? Eg: a,b=b,a

[@lamchingrou9464]

do you have any strategies to identify edge cases like how we are not supposed to increment the i pointer if we do a swap with the right pointer, or must we have done this question before?

[@dheepthaaanand3214]

While swapping 0s to the left portion, we would never encounter a scenario where we are swapping 0 with a 2 because we have already dealt with the left portion and it won't contain 2s. However, while swapping 2s to the right portion, there is a chance of swapping it with a 0

[@yuxinyang2608]

it's is so cool ,btw there are also another case that if we swap 2 with 2 , which means 2 still in i position , so we should also put i in original position till r -1

[@Raj10185]

Thank you so much neetcode its also known as Dutch flag algorithm

[@rohitjha2435]

man i wish u reach 1 million as early as possible

[@ShekharPrasadRajak]

I think we only need to increment i when we have 1 ( or after swapping left side or right side ) in i’th index . Because the case mentioned for swapping with right pointer , can happen for left pointer swap as well(when we left point was 2)

[@wayne4591]

No, it won't. Please note that in the case we discuss, the i cursor is already on the right of the left pointer, that means the i cursor already encounter the left pointer number. If that number were 2, we would have moved this 2 to the end of the array. So, there won't be a case where the left pointer is pointing to a 2, as long as the i cursor is on the right of the left pointer.

[@ajitsdeshpande]

Thank you for all the efforts in explaining and coding out the solutions. They have helped me a lot. All the Best! 👍

[@NeetCode]

Thank you so much!!!

[@eba-pachi]

This seems a bit simpler: class Solution: def sortColors(self, nums: List[int]) -> None: buckets = [0, 0, 0] for color in nums: buckets[color] += 1 offset = 0 for color in range(len(buckets)): n = buckets[color] for i in range(offset, offset + n): nums[i] = color offset += 1 and it runs in linear time too

[@calebyenusah3174]

This is the Dutch national flag problem. Check the algorithm out on Wikipedia.

[@木漏れ日-v9n]

You can swap in one line in Python: a, b = b, a

[@5pellcast3r]

thanks for explaining why we don't move the mid pointer when moving the high pointer

[@staceyonuora5329]

Because we need to check what the mid pointer was swapped with. If it was a 0 or 1 or 2 again we need to perform more actions on that index

[@noa.leshem]

Probably failed an interview over this today! and the interviewer just would not let me use count sort 😭

[@nikhilnagarapu3077]

Understood the base case very well! Thank you!!

[@sabukuna]

var sortColors = function(nums) { let bucket = new Array(3).fill(0); let indx = 0; for(let i = 0; i < nums.length; i++){ bucket[nums[i]]++ } for(let i = 0; i < nums.length; i++){ while(bucket[indx] == 0) indx++; nums[i] = indx bucket[indx]-- } }

[@lestode4816]

I have a very simple solution: just count the number of 0, 1 and 2, make sure that nums = [0]*numsOfRed + [1]*numsOfWhite + [2]*numsOfBlue and voilà :)

[@neks2081]

The problem asks to do it in place and in one pass, you are doing neither

[@lestode4816]

@@neks2081 The problem on leetcode doesn't ask it to do it in one pass. I do it in place, since I update the passed array.

[@simonkim22]

Thanks for the great explanation but isn’t the first solution considered as counting sort more specifically since there’s no dynamic allocation required as the values in each bucket will be the same? I know it’s not really that important in this context but just wanted to clarify to avoid confusion. Your explanation was on point regardless tho 😀

[@servantofthelord8147]

Was thinking the same thing too.

[@anandsharma16]

brute force approach- class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ nums2 = [] nums3 = [] nums4 = [] for i in nums[:]: if i == 0: nums2.append(i) elif i == 1: nums3.append(i) else: nums4.append(i) nums[:] = nums2 + nums3 + nums4

[@PremPal-uy4nm]

""" I tried to understand why edge case is happening. Bellow is my understanding. Might not be fully correct but if someone can check this we might able to verify. If interested please paste these text in some editor(preferably in jupyter notebook) and check """ """ O(N) time O(N) space - Single Pass 1.Basically we are using 3 pointer format. -left pointer designate that all the 0 are on it's left -right pointer designate that all the 2 are on it's right -middle pointer taking caser of 1 in middle 2. One special edge case here [0,1(l),2(m),1,0(r),2] -This edge case happens when middle pointer points to 2 here. In This case 2 wll be swapped with r. When it happens 0 will be hanging in middle. Why it is happening? To understand this We first need to understand what is actual role of l,m & r pointers. 1.m is main pointer here. It tells how and when to swap. 2.left having chance to point 0 or 1 at any random time. 3.m having chance to point 0,1 or 2 at any random time. 4.r also having chance to point 0,1 or 2 at any random time. 5.t means that when m pointer swaps with r pointer any of there values (0,1,2) can take its place in middle. -if 1 comes in middle, no issue because we want one 1 in middle. -if m points 0 then left pointer is already taking care of 0 - no issue here also. -But if m points to 2 then all 3 values can take it place at any random time- 0 or 1 or 2. This happens because of point 3 and 4 above. -when it is replace by 1 no issue here. -but if is replaced by 0 then m will move one step again and then 0 will be hanging there in middle -If it is replaced by 2 then again 2 will be hanging in middle just like 0 -Above hanging happens when it points to 2 only(reason being possibility of all 3 number appearing at this place) .This can be avoided if we don't move m pointer in this case. """ def sortColors(nums): l,r=0,len(nums)-1 m=0 while m

[@sodo3872]

How can we intuitively remember that there is this edge case to not move the i cursor after swapping with moving the right pointer? Great video. Thank you!

[@wayne4591]

basically, you can't really think of this edge case when you first code this problem. I think the trickiest part of this problem is to move the i only when encounter 0 and 1.

[@naumraviz4772]

You make my life easier thanks for that

[@vdyb745]

Thank you for this explanation !!!

[@nirmalgurjar8181]

Isn't second approach also 2 pass ? i pointer is scanning once then followed by r and l combined. technically that should also be called 2 pass algorithm. little confused.

[@Manu-et6zk]

python swap : x,y = y,x

[@NeetCode]

Yup good point, forgot about that.

[@basic-2-advance]

What tool does neetcode use while drwaing the explanation?

[@Cool-ss7ph]

My C++ Solution which is also of O(n): void sortColors(vector& nums) { int n0=0,n1=0,n2=0; for(int i=0;i

[@NexushasTaken]

no, it's O(n²), cuz vector.insert takes O(n)

[@haoli8983]

bucket sort create a map or array to store how many numbers. it doesn't mean use extra memory ?

[@AlexSmith-mr4ps]

if you created a map or array, it would use more memory than this approach.

[@TheBestNameEverMade]

Quick sort is n^2

[@its_me_tabs]

Someone please tell me why would this be unacceptable It satisife severything the question wants. nums[:] = [0]*nums.count(0)+[1]*nums.count(1)+[2]*nums.count(2)

[@thatdude6569]

What will be the approach if there are n number of colours?

[@KeepCoding69]

In that case, it becomes a normal sorting array question. So, you will have to use sorting algorithms like merge sort,etc.

[@raz_dva_]

I slept in the middle.. that is not easy to understand explanation.

[@CoDestination]

kzbin.info/www/bejne/sJPMmoZ3brV0h9Usi=BlCmE97W_9QGnAoi

[@sarthak.purohit]

Time complexity of his code using quickSort in one pass is O(n), right?

[@konradhunter1407]

Yes. The bucket method is also O(n).

[@dennisgatere7821]

Looks like a great problem to use counting sort since there are only 3 values and guaranteed to never be anything else

[@dennisgatere7821]

public void sortColors(int[] nums) { int[] count = new int[3]; for (int num : nums) { count[num]++; } for (int i = 0, j = 0; i < count.length; i++) { while (count[i] > 0) { nums[j++] = i; count[i]--; } } } Beats 100% of solutions!!

[@krishc.1808]

As Neetcode said in the video, counting sort is a completely valid solution. But, since it's relatively easy to come up with, interviewers are more likely going to ask you for the one-pass implementation.

[@kartd02606]

thank you

[@saiprathek]

mind bengindi mawa

[@08JuHan]

very helpful again :D

[@akurnya]

dutch national flag problem

[@mingjuhe1514]

Tnanks bro!

[@theonlyvish]

Time complexity: O(n)?

[@MatheusLopesCoder]

you are fking brilliant, thank youuu

[@parminpatel8337]

did nums.sort() and called it a day! but then I came here to be saved

[@georgebrooking3820]

Excellent explanation, edge case hard to wrap head around though. 😂. What if after a swap, 'L' is pointing to a 2? You said 'L' can only be pointing to a '1' no matter what...

[@georgebrooking3820]

The confusion here is, how do we know that 'R' can point to (0,1,2)? What about 'L'? Why is L only capable of pointing at a (0,1)?

[@georgebrooking3820]

This forward pass + backward pass solution using '1' as a pivot value is more intuitive without the need to think about that darn edge case: public void sortColors(int[] nums) { //forward pass int start = 0; for(int i = 0; i < nums.length; i++){ if(nums[i] < 1){ swap(nums, i, start); start++; } } //backward pass int end = nums.length-1; for(int i = nums.length-1; i >= 0; i--){ if(nums[i] > 1){ swap(nums, i, end); end--; } } } public static void swap (int[] nums, int i, int j){ int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }

[@neks2081]

L can never point at 2, it is impossible i pointer is always ahead of L and it would have swapped out the 2 so L doesn’t have a chance to point at it

[@sidazhong2019]

I just used normal quicksort method beat 90% other solutions. Or maybe using bucket sort. I will definitely avoid this 3 pointers weird edge cases ...

[@edwardteach2]

U a God class Solution(object): def sortColors(self, nums): """ :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. """ l, r = 0, len(nums)-1 i = 0 while i

[@numberonep5404]

damn this is good

[@geekydanish5990]

Ig anyone looking for bucket sort hash_map = {0:0, 1:0, 2:0} for num in nums: hash_map[num] = hash_map.get(num, 0) + 1 for i in range(hash_map[0]): nums[index] = 0 index += 1 for i in range(hash_map[1]): nums[index] = 1 index+=1 for i in range(hash_map[2]): nums[index] = 2 index+=1