Back To Back SWE Hi , I have seen many of your videos those are really good . In this one , I would like to understand why we need to do summation . I have tried to come up below solution without doing summation it passed all the testcases on leetcode . Am I missing something class Solution { public List sortArray(int[] nums) { if(nums == null || nums.length == 0){ return null; } return countingSort(nums); } private List countingSort(int[] nums) { Integer maxNum = null; Integer minNum = null; int [] countingSortPositive = null; int [] countingSortNegative = null ; for (int index = 0; index < nums.length; index++) { int value = nums[index]; if(value >=0){ if(maxNum == null){ maxNum = value; }else{ maxNum = Math.max(maxNum, value); } }else { if(minNum == null){ minNum = value; }else{ minNum = Math.min(minNum, value); } } } if(minNum != null){ countingSortNegative = new int[Math.abs(minNum) + 1]; } if(maxNum != null){ countingSortPositive = new int[maxNum + 1]; } for (int i = 0; i < nums.length; i++) { int value = nums[i]; if(value >=0){ countingSortPositive[value]+= 1; }else { countingSortNegative[Math.abs(value)]+=1; } } List list = new ArrayList(); if(countingSortNegative != null && countingSortNegative.length > 0){ for (int i = countingSortNegative.length -1 ; i >=0; i--) { if(countingSortNegative[i] != 0){ for (int j = 0; j < countingSortNegative[i]; j++) { list.add(-i); } } } } if(countingSortPositive != null && countingSortPositive.length > 0){ for (int i = 0; i < countingSortPositive.length; i++) { if(countingSortPositive[i] != 0){ for (int j = 0; j < countingSortPositive[i]; j++) { list.add(i); } } } } return list; } }

I haven't replied to this for a bit, replying to close this out in my "unresponded to comments" feed.

Sorry to be so offtopic but does anybody know a trick to get back into an instagram account? I somehow lost the login password. I would love any tips you can give me.

Aw, thanks

The running sum step is not necessary, it is only one version of counting sort (the more commonly seen one which is why I covered it). You could just create an occurrence array and from there go straight to placement. The asymptotic complexity is still the same. Why would duplicated elements necessitate the aggregation step?

@@BackToBackSWE you're right, it's possible to do it without performing a sumation if we're sorting just numbers like in your video. Although I still think it makes it easier to understand if you have duplicates in the array, see this visualization: kzfaq.info/get/bejne/beCletB8y7vYZ6c.html

Yes, that's the version we covered ... I'm still confused on how duplicates change anything. We would always be sorting positive integers (whether we codify actual objects/any other non-integer value we want to sort into an integer mapping). Can you clarify, I must be missing something

@@BackToBackSWE ok maybe it was just me but after watching your video I wasn't completely sure why running sum step was needed. But if you perform this algorithm on an array with duplicates, you see that running sum array is actually useful, it helps to place a correct amount of a given element in the final array. Sorry for not being clear enough before :) As for the difference between sorting just integers vs some other structures, see this post because it explains it a lot better than I could (it also touches the topic of cumulative sum): stackoverflow.com/a/32235015

@@mzmzgreen Ahhhhhh, gotcha. That link cleared it all up. Yes, you are right, that is why the aggregation sum step is needed (in the case we are not sorting just raw numbers) - so we can go to the original array and place objects in the right index (and at that point the 'count' array will be a literal "guide" for us to know where to put what based on its key integer value). Dang, I learned something, thanks

Nah, I dun goofed

nice

it does not work for duplicate numbers i think.. Since there are no negative indices any way pls tell me how to implement this for negative numbers as well.

​@@shreevatsalamborghin int max = Arrays.stream(a).max().getAsInt(); int min = Arrays.stream(a).min().getAsInt(); int range = max-min+1; int [] count = new int[range]; int [] output= new int[a.length]; //store count of each character for(int i=0;i

thx

Great to hear!

Appreciate that!

thx

hey

Back To Back SWE hey

Happy to hear that!

sure

Thank you sir you replied it's a great pleasure to me

Thank you!

sure

thanks

yes, thank you

sure

Thanks and I almost made one but go too busy during the semester, yeah i can

@@BackToBackSWE nice. Looking forward to it! thanks Ben for all great videos. One thing that would be great to include in that video would be when should you use Counting sort vs Radix sort? I figured when you have input like [ 0, 11111111111111111] counting sort would perform slow vs it would be very easy for radix sort.

ye

ok

By the way prefix sums ONLY NEEDED WHEN WE HAVE DUPLICATE VALUES IN THE ORIGINAL ARRAY to avoid extra nested loop while reconstruction your sorted arrays.

And you forgot to mention why we started reconstruction the sorted array by traversing from the end of the array. The reason is to preserve the STABILITY of the array. You can start from the beginning, in that case the stability of the array is not preserverd

nice

sure!

ye

sure

Yeah, my bad. Code in description to clarify but yeah, my fault for that, I got lazy.

The repository is deprecated - we only maintain backtobackswe.com now.

You can check out the code repository on backtobackswe.com/

It is just the more common implementation, you can go the other way too

@@BackToBackSWE It also makes the implementation of a sorting algorithm stable if you iterate backwards

Not sure when I'll do that, I'm just winging it right now

Repository is deprecated and no longer maintained

I am at 7:32 , and still understand everything

ok

ok

I don't remember the code for this to be honest

im not sure, I forgot counting sort since I shot this, I need a refresher

Counting sort is most effective when 1) You know the range your values will be in 2) You're comfortable with the space implications of building a count array of the size of the range. (Space tradeoff) In this case it seems you're not sure what range your values may be in. Moreover, even if you were, 10^6 values would mean a lot of space and time to build a count array (Assuming little to no duplicate values i.e all 10^6 are fairly unique.)

@@bolu3307 thanks

yes

sure

yeah

yes

yeah we can

Actually found out the reason: 1. When we use counting sort as a subroutine in radix sort, we need to maintain the relative ordering, there we must traverse from the back otherwise, radix sort fails. That's the reason! Love your videos man. Thanks.

@@arunm619 nice

how was the exam - got to this late

I don't think I passed. I guess they thought we would all cheat and made it extra hard. I figured it out in case this could help someone: To order in non increasing manner: For i=k-1 down to 0 { C[i] = C[i] + C[i+1] } K being the length of the C array.

yeah, you're right

I think I forgot, ya got me. But yeah, it is as stated, if we can map an object to an integer (or establish that relationship in any way) then we can sort the data based on those integer mappings. I just forgot to do an example of it but it is the same thing.

I don't want to

Back To Back SWE not fair dawg

Correct, I think it is a matter of specificity because they are different parameters. Asymptotic bounds do ignore constants (by their very definition of picking an arbitrary c to multiply by f(n) to bound T(n)), but even if n upper bounds k, it is still not a constant. It should be considered in the asymptotic notation since it is another parameter that an external caller can modulate. The end behavior is linear through and through, hence "linear time".

@@BackToBackSWE Thanks a lot for the detailed reply!

yeah I know - I have a memory of every video I didn't make all I wished it could be. This is one of them

I don't remember to be honest, I'd have to recap on counting sort

I think it's 3, from how I understood it

k would represent the range of nos so max - min +1 = 5001

5001 , here counting sort is not efficient

nice

I think it is somewhere

Back To Back SWE 😂. Oh okay I see how it is naowwwww 😂

yes that's normal - the amount of leetcode you do has a very loose correlation to preparedness. It's not about problem count - it's about topic comprehension. 1.) It depends, when studying you may just fundamentally not have the toolset to solve a problem, so trying can waste your time if even the brute force is locked from you. A problem like this is kind of bad since it doesn't demonstrate critical thinking...but you can often recognize it. If you know you can brute force you do that and then maybe give it 10-20 min beore you give up? really up to judgement. 2.) I'd want to deeply understand the solution, why it works, and the principles it has taught me to apply elsewhere. Some problems are good for this and some are less useful. 3.) I'd check the solutions to see if there was a more optimal way.

ok

yeah u rite

Did I say that? Don't remember, if so thanks for the catch.

@@BackToBackSWE np. between 2:21-2:26.

ok