At 12:34 the cumulative sum should start at 1 na because bucket[i] = bucket[i] + bucket[i-1] bucket[1] = bucket[1] + bucket[1-1] bucket[1] = 1 + 0 bucket[1] = 1
The cumulative sum should start at 1 means bucket[i]=bucket[i]+bucket[i-1]; bucket[1]=bucket[1]+bucket[0]]; bucket[1]=0+1=1 but, u write bucket [1]=0 ; how ? can you please explain
@@gokulakannan3664 it is because when you are gonna check for how many numbers are less than a a certain number in the bucket you would do bucket[value -1]
Let me give an example suppose. 1,2,3 in the bucket we we would have [0,1,1,1] meaning there is 1 1 there is 1 2 there is 1 3 so now if you think about it to know how numbers are less than 2 we just need to know the frequency of the previous numbers which is n - 1 so bucket[1] = 1 + 0 because there are because if you want to find how many numbers are less than 2 you would do bucket[2 - 1] which would give you 1 which is the numbers of numbers less than 2 it took me a while to understand but thing about it like this we have a array of the numbers and the frequencies and when we start from 1 in the loop and going bucket[1] += bucket[1 - 1 = 0] we are just getting the number of 0s in the array which is the number of values less than 1 so on. so now when we access bucket[n -1] we get all the numbers less than that number hopefully this makes sense
Thanks for the explanation! This is so neat! You deserve more views. I have one doubt though. If there is a very huge number in the array, then to do the cumulative sum we will require a very long iteration on the frequency array. So, the time complexity will be O(max(given array)). Won't that be problematic?
Hi Partho, your concern is very valid...that is why if you read the problem statement it says that the range of numbers is between 1-100. If the range is very large, just like your example...then yes..this method will not be an efficient one. At that point of time, we might need to compromise with the space complexity or the time complexity. so, there cannot be a optimal solution that works for all scenarios. Each problem gets unique on it own way... :)
in count smaller number than each element for loop how bucket[1] = 0???????????????? if we calculate bucket[1]=bucket[1]+bucket[1-0] doesnt that will give us bucket[1]=1+0 which will be bucket[1] = 1.
Your explanation is different from the code you wrote, i am talking about the part in in which you are counting the smaller number and populate the result as you are saying that we have to take the bucket[nums[i]] as per your explanation but you are using bucket[nums[i]-1] in your code which shows somewhere your explanation is different from the code and beginner might get confused from this other than this your explanation is good @Nikhil Lohia
The cumulative sum should start at 1 means bucket[i]=bucket[i]+bucket[i-1]; bucket[1]=bucket[1]+bucket[0]]; bucket[1]=0+1=1 but, u write bucket [1]=0 ; how ? can you please explain
@@milindvedithebunkerboy4914 I was also confused by this. I think @nikoo28 may have made a mistake in drawing the explanation. The actual bucket counts end up being [0, 1, 3, 4, 4, 4, 4, 4, ...] not as it seems in the drawing [0, 0, 1, 3, 4, 4, 4, 4, 4, ...]. But this is resolved by the "populate the result" section of the code where result is found by subtracting 1 from the index: result[i] = buckets[nums[i] - 1]; Hope this helps.
@@nikoo28 question is very easy but the way you explained, it becomes very tough and you have never explained the cumulative addition part correctly, so many students also commented on this part as well.
@@shankarvishalsharma I understand the confusion. There is a small error in my explanation on that part. Basically you have to calculate the cumulative sum. You can easily do it in the array. Really sorry for the error in the visual.
Searching for the explanation for the intution part! Great explanation !!
At 12:34 the cumulative sum should start at 1 na because
bucket[i] = bucket[i] + bucket[i-1]
bucket[1] = bucket[1] + bucket[1-1]
bucket[1] = 1 + 0
bucket[1] = 1
The cumulative sum should start at 1 means
bucket[i]=bucket[i]+bucket[i-1];
bucket[1]=bucket[1]+bucket[0]];
bucket[1]=0+1=1
but, u write bucket [1]=0 ; how ? can you please explain
@@gokulakannan3664 exactly, I also have the same Q
@@gokulakannan3664 it is because when you are gonna check for how many numbers are less than a a certain number in the bucket you would do bucket[value -1]
Let me give an example suppose. 1,2,3
in the bucket we we would have [0,1,1,1]
meaning there is 1 1 there is 1 2 there is 1 3
so now if you think about it to know how numbers are less than 2 we just need to know the frequency of the previous numbers which is n - 1
so bucket[1] = 1 + 0 because there are because if you want to find how many numbers are less than 2 you would do bucket[2 - 1] which would give you 1
which is the numbers of numbers less than 2
it took me a while to understand but thing about it like this we have a array of the numbers and the frequencies and when we start from 1 in the loop and going bucket[1] += bucket[1 - 1 = 0] we are just getting the number of 0s in the array which is the number of values less than 1 so on.
so now when we access bucket[n -1] we get all the numbers less than that number
hopefully this makes sense
Great explanation and production! Subscribed, Keep up the good work!
best explanation for beginners like me thanks man
Such a simple yet efficient explanation! Thank you so much. Keep it up!!
Thanks for the explanation! This is so neat! You deserve more views. I have one doubt though. If there is a very huge number in the array, then to do the cumulative sum we will require a very long iteration on the frequency array. So, the time complexity will be O(max(given array)). Won't that be problematic?
Hi Partho,
your concern is very valid...that is why if you read the problem statement it says that the range of numbers is between 1-100. If the range is very large, just like your example...then yes..this method will not be an efficient one. At that point of time, we might need to compromise with the space complexity or the time complexity.
so, there cannot be a optimal solution that works for all scenarios. Each problem gets unique on it own way... :)
Oh yes! My bad! Some how I overlooked that constraint thinking it is trivial. Thanks for your clarification :)
Awesome!! But Code you written in left and logic you explained is different.
As per code you have doing a 1 less count to pick the value.
Best Explanation !!
Greate Explaining Bro
Extremely helpful video
Wonderful
in count smaller number than each element for loop how bucket[1] = 0???????????????? if we calculate bucket[1]=bucket[1]+bucket[1-0] doesnt that will give us bucket[1]=1+0 which will be bucket[1] = 1.
Thanks
Great explanation thanks
Glad I could help
Your explanation is different from the code you wrote, i am talking about the part in in which you are counting the smaller number and populate the result
as you are saying that we have to take the bucket[nums[i]] as per your explanation but you are using bucket[nums[i]-1] in your code which shows somewhere your explanation is different from the code and beginner might get confused from this other than this your explanation is good @Nikhil Lohia
my major focus is usually on the problem solving part. If you understand that, writing code should be easy :)
Why bucket size is 102 ?
what if the elements are negative, then it fails..
There are 2 constraints in the leetcode problem, so no negative numbers.
Constraints:
2
yes, always check constraints...
The cumulative sum should start at 1 means
bucket[i]=bucket[i]+bucket[i-1];
bucket[1]=bucket[1]+bucket[0]];
bucket[1]=0+1=1
but, u write bucket [1]=0 ; how ? can you please explain
Where do you see bucket[1] = 0?
@@nikoo28 10:49
That is not the bucket count. You need to see the total numbers to the left. Because you have to find numbers smaller than current.
but the way you are calculating is bucket[i] - bucket[i - 1] thats gives 1
@@nikoo28
@@milindvedithebunkerboy4914 I was also confused by this. I think @nikoo28 may have made a mistake in drawing the explanation.
The actual bucket counts end up being [0, 1, 3, 4, 4, 4, 4, 4, ...] not as it seems in the drawing [0, 0, 1, 3, 4, 4, 4, 4, 4, ...].
But this is resolved by the "populate the result" section of the code where result is found by subtracting 1 from the index: result[i] = buckets[nums[i] - 1];
Hope this helps.
language ka mane likh de kar na m.... b...
Bad explanation 😢😢😢
what part did you face a problem with?
@@nikoo28 question is very easy but the way you explained, it becomes very tough and you have never explained the cumulative addition part correctly, so many students also commented on this part as well.
@@shankarvishalsharma I understand the confusion. There is a small error in my explanation on that part. Basically you have to calculate the cumulative sum. You can easily do it in the array. Really sorry for the error in the visual.