Sort Colors - Quicksort Partition - Leetcode 75 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: leetcode.com/problems/sort-co...
0:00 - Read the problem
4:14 - Drawing Explanation
13:00 - Coding Explanation
leetcode 75
This question was identified as a facebook coding interview question from here: github.com/xizhengszhang/Leet...
#quicksort #partition #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@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!

[@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.

[@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!

[@shenzheng2116]

Excellent explanation! Your channel deserves 1 billion subscribers :)

[@expansivegymnast1020]

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

[@nikhilnagarapu3077]

Understood the base case very well! Thank you!!

[@rishikaverma9846]

Cannot imagine solving leetcode without your solutions

[@vdyb745]

Thank you for this explanation !!!

[@hieu8276]

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

[@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?

[@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!!!

[@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

[@naumraviz4772]

You make my life easier thanks for that

[@08JuHan]

very helpful again :D

[@mingjuhe1514]

Tnanks bro!

[@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

[@kartd02606]

thank you

[@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.

[@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 😀

[@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

[@calebyenusah3174]

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

[@MatheusLopesCoder]

you are fking brilliant, thank youuu

[@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

[@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.

[@numberonep5404]

damn this is good

[@haoli8983]

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

[@saiprathek]

mind bengindi mawa

[@BasicToAdvance_101]

What tool does neetcode use while drwaing the explanation?

[@noa.leshem]

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

[@Manu-et6zk]

python swap : x,y = y,x

[@NeetCode]

Yup good point, forgot about that.

[@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.

[@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.

[@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 ...

[@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.

[@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

[@TheBestNameEverMade]

Quick sort is n^2

[@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

[@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).

[@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

[@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)

[@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.

[@raz_dva_]

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

[@CoDestination]

kzbin.info/www/bejne/sJPMmoZ3brV0h9Usi=BlCmE97W_9QGnAoi

[@theonlyvish]

Time complexity: O(n)?

[@akurnya]

dutch national flag problem

[@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

[@parminpatel8337]

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

[@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