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).
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!
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
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!
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?
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.
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
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)
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.
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 😀
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!
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.
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
""" 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):
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.
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à :)
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...
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; }
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.
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
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
Your videos are by far the best explanations I have seen on RUclips so far. Concise and straightforward. Thank you very much! Keep it coming. 😀
Thanks! Happy they are helpful!
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).
Thanks for this comment. Saved me so much time.
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!
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
Another banger. You're gonna help me get employed in the tech industry.
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!
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?
Cannot imagine solving leetcode without your solutions
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.
Omg. First time heard of “bucket sort” and instantly got a use case in reality. Very nice video ❤
Excellent explanation! Your channel deserves 1 billion subscribers :)
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
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)
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.
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 😀
Was thinking the same thing too.
Thank you for all the efforts in explaining and coding out the solutions. They have helped me a lot. All the Best! 👍
Thank you so much!!!
Understood the base case very well! Thank you!!
Thank you so much neetcode its also known as Dutch flag algorithm
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!
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.
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
thanks for explaining why we don't move the mid pointer when moving the high pointer
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
man i wish u reach 1 million as early as possible
Thank you for this explanation !!!
What tool does neetcode use while drwaing the explanation?
Probably failed an interview over this today! and the interviewer just would not let me use count sort 😭
"""
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
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.
bucket sort create a map or array to store how many numbers. it doesn't mean use extra memory ?
if you created a map or array, it would use more memory than this approach.
This is the Dutch national flag problem. Check the algorithm out on Wikipedia.
You make my life easier thanks for that
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à :)
The problem asks to do it in place and in one pass, you are doing neither
@@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.
Time complexity of his code using quickSort in one pass is O(n), right?
Yes. The bucket method is also O(n).
python swap : x,y = y,x
Yup good point, forgot about that.
What will be the approach if there are n number of colours?
In that case, it becomes a normal sorting array question. So, you will have to use sorting algorithms like merge sort,etc.
Tnanks bro!
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...
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)?
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;
}
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
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
very helpful again :D
thank you
Quick sort is n^2
you are fking brilliant, thank youuu
Looks like a great problem to use counting sort since there are only 3 values and guaranteed to never be anything else
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!!
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.
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 ...
Time complexity: O(n)?
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
no, it's O(n²), cuz vector.insert takes O(n)
mind bengindi mawa
I slept in the middle.. that is not easy to understand explanation.
ruclips.net/video/zbiiSA9PAQs/видео.htmlsi=BlCmE97W_9QGnAoi
damn this is good
did nums.sort() and called it a day! but then I came here to be saved
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
dutch national flag problem
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