Numbers Smaller than current Number (LeetCode 1365) | Full solution with examples | Study Algorithms

[@gocrazy6177]

Searching for the explanation for the intution part! Great explanation !!

[@raizo4203]

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.

[@maheshnahak9510]

Great explanation and production! Subscribed, Keep up the good work!

[@srbsnkr]

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.

[@hi-tk4hu]

best explanation for beginners like me thanks man

[@princesoni7371]

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

[@nikoo28]

my major focus is usually on the problem solving part. If you understand that, writing code should be easy :)

[@naamnhibataunga5897]

what if the elements are negative, then it fails..

[@prashanthshetty8337]

There are 2 constraints in the leetcode problem, so no negative numbers. Constraints: 2

[@nikoo28]

yes, always check constraints...

[@sanketsaitawdekar4440]

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

[@gokulakannan3664]

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

[@hoddybhaba6704]

@@gokulakannan3664 exactly, I also have the same Q

[@pythonwithsean]

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

[@pythonwithsean]

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

[@parthoroychoudhury860]

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?

[@nikoo28]

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

[@parthoroychoudhury860]

Oh yes! My bad! Some how I overlooked that constraint thinking it is trivial. Thanks for your clarification :)

[@cricketmiles]

Why bucket size is 102 ?

[@vinaythota3684]

Greate Explaining Bro

[@sahilbisht3661]

Best Explanation !!

[@subee128]

Thanks

[@memes.co_om]

language ka mane likh de kar na m.... b...

[@pranjalsingh5047]

Extremely helpful video

[@aashnasinha6537]

Such a simple yet efficient explanation! Thank you so much. Keep it up!!

[@shankarvishalsharma]

Bad explanation 😢😢😢

[@nikoo28]

what part did you face a problem with?

[@shankarvishalsharma]

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

[@nikoo28]

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

[@mensajemexico]

Great explanation thanks

[@nikoo28]

Glad I could help

[@gokulakannan3664]

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

[@nikoo28]

Where do you see bucket[1] = 0?

[@gokulakannan3664]

@@nikoo28 10:49

[@nikoo28]

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.

[@milindvedithebunkerboy4914]

but the way you are calculating is bucket[i] - bucket[i - 1] thats gives 1 @@nikoo28

[@Strictly_biz]

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

[@horse_butt]

Thank you! The best explanation I've seen so far! Finally I can see how counting sort helps to solve this problem

[@nikoo28]

You're very welcome!