Sort Colors - Quicksort Partition - Leetcode 75 - Python

0:00 - Read the problem
4:14 - Drawing Explanation
13:00 - Coding Explanation

leetcode 75

#quicksort #partition #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[frankl]

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

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

[jhs]

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

[peterkim]

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!

[expansivegymnast]

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

[shenzheng]

Excellent explanation! Your channel deserves 1 billion subscribers :)

[nikhilnagarapu]

Understood the base case very well! Thank you!!

[lamchingrou]

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?

[rishikaverma]

Cannot imagine solving leetcode without your solutions

[saigouthamipriyankaraparth]

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

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

[hieu]

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

[yuxinyang]

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

[ajitsdeshpande]

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

[simonkim]

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 😀

[naumraviz]

You make my life easier thanks for that

[sodo]

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!

[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

[Raj]

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

[haoli]

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