Table of Contents: Introducing Counting Sort 0:00 - 2:08 Walking Through The Algorithm 2:08 - 3:18 Step 1: Initialize Occurrence Array 3:18 - 3:27 Step 2: Count Occurrence In The Original Array 3:27 - 4:34 Step 3: Aggregation of Occurrences 4:34 - 6:28 Why Did We Just Do That? 6:28 - 7:54 Step 4: Placements 7:54 - 10:14 Sorting Finished. 10:14 - 11:52 Analyzing Counting Sort 11:52 - 15:43 We Get The Final Bound 15:43 - 16:10 Wrap Up 16:10 - 17:08 The code for the problem is in the description. Fully commented for teaching purposes.
@AnshulSharma-vw9wu4 жыл бұрын
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; } }
@BackToBackSWE4 жыл бұрын
I haven't replied to this for a bit, replying to close this out in my "unresponded to comments" feed.
@judekye16793 жыл бұрын
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.
@apatt555 жыл бұрын
Landed a job last month and relied on your videos a lot. Just donated some money to your Patreon. Thanks for everything!
@BackToBackSWE5 жыл бұрын
Aw, thanks
@mzmzgreen5 жыл бұрын
Nice explanation. You could've picked other example - the one that contains duplicated elements. It would make it easier to understand why the running sum array is needed.
@BackToBackSWE5 жыл бұрын
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?
@mzmzgreen5 жыл бұрын
@@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: kzbin.info/www/bejne/bavYeKCBm7qnbdU
@BackToBackSWE5 жыл бұрын
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
@mzmzgreen5 жыл бұрын
@@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
@BackToBackSWE5 жыл бұрын
@@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
@philipdimeski51885 жыл бұрын
Is it just me or is this algorithm just confusing in general? I reckon you did a good job explaining it as a simply as possible! No matter what resource I look at this algorithm just does not make sense to me hahah.
@BackToBackSWE5 жыл бұрын
Nah, I dun goofed
@Charles-rn3ke5 жыл бұрын
The example you use is too special and not general
@BackToBackSWE5 жыл бұрын
Yeah, my bad. Code in description to clarify but yeah, my fault for that, I got lazy.
@xuehaizhou83354 жыл бұрын
Your explanation is pretty good, but the example you use is too simple which occurs some confusion. Thank you anyways.
@BackToBackSWE4 жыл бұрын
yeah
@jakejreid4 жыл бұрын
Has the code been removed?
@BackToBackSWE4 жыл бұрын
The repository is deprecated - we only maintain backtobackswe.com now.
@samuelbarks14 жыл бұрын
in CLRS it says that K represents the range of the input from (O, K) not how many unique elements there are
@BackToBackSWE4 жыл бұрын
ok
@minar75554 жыл бұрын
Your explanation of K is wrong. K is not the number of unique values in the input array. If it were so, for example, for an input array [1,0,2,999], your count array would be [0,0,0,0] i.e have index 0 to 3. This will not work as the program will not be able to access count[999] and increment occurrences. K is the max value in the input array. So the count array should, in this case, be of size -999- 1000 edit: size = k+1 = 1000
@BackToBackSWE4 жыл бұрын
Did I say that? Don't remember, if so thanks for the catch.
@minar75554 жыл бұрын
@@BackToBackSWE np. between 2:21-2:26.
@uzboxing52384 жыл бұрын
I think the terminology of prefix sums is used widely, i was confused with running sums, but in the end I got it that it was actually prefix sums that I learned for other algorithm before.
@uzboxing52384 жыл бұрын
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.
@uzboxing52384 жыл бұрын
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
@BackToBackSWE4 жыл бұрын
nice
@DensonGeorge185 жыл бұрын
Can you explain why we iterate backwards while doing placements in the original array?
@BackToBackSWE5 жыл бұрын
It is just the more common implementation, you can go the other way too
@anzeha985 жыл бұрын
@@BackToBackSWE It also makes the implementation of a sorting algorithm stable if you iterate backwards
@abracham33375 жыл бұрын
I've seen many implementations but only this one matches with my uni's and is fairly understandable. ^^ Thank you, keep up the good work !
@BackToBackSWE5 жыл бұрын
nice
@shreevatsalamborghin4 жыл бұрын
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.
@tawhidshahrior88043 жыл бұрын
@@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
@vishpatel39805 жыл бұрын
Great explanation Ben! One can easily follow :). do you have radix sort explanation video created? if not, can you please create one for Radix sort ?
@BackToBackSWE5 жыл бұрын
Thanks and I almost made one but go too busy during the semester, yeah i can
@vishpatel39805 жыл бұрын
@@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.
@elisabetta84034 жыл бұрын
You should have a zero and well other numbers that aren't 1 in your c array. Any idea on how to write code to sort in descending order (exam tomorrow)?
@BackToBackSWE4 жыл бұрын
how was the exam - got to this late
@elisabetta84034 жыл бұрын
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.
@ankitratnam4 жыл бұрын
We can actually modify the counting sort to even include -ve integers as well. For that we can use extra space in the same array with one partition for +ve integers and one for -ve. and when we finally count the numbers we start from the 2nd partition (which has negative integers stored only their +ve magnitude which will be converted to -ve when producing output from the partition 2) and then after completing it we use the first partition for +ve integers.
@BackToBackSWE4 жыл бұрын
yes, thank you
@MIRMOHAMMADREZAHEIDARZADNAMIN4 ай бұрын
ZERO is a non negative integer not a positive integer. The upper bound for the second and forth summation should be n not n-1. You are not a professor my friend, when you don't know something correctly, don't make such video clips and waste our time.
@TeeheeTummytums5035 жыл бұрын
any plans for tackling 621. Task Scheduler in leetcode?
@BackToBackSWE5 жыл бұрын
Not sure when I'll do that, I'm just winging it right now
@antonmyshenin9424 Жыл бұрын
Given k - unique values and n - all values, we could conclude that k
@xxsurajbxx4 жыл бұрын
Very underrated educational content. I just subscribed and hope to learn more programming concepts. Keep it up
@BackToBackSWE4 жыл бұрын
thx
@n.h.son19023 ай бұрын
8:02, why do we move backwards in the array arr? Is there any reason behind this? Why not moving forwards?
@Shirani0073 жыл бұрын
Please stop teaching, teaching is an art, and it is just your assumption that you can teach. + even if you want to do it, prepare on paper first and then record. Thank you
@josephluce72815 жыл бұрын
Confusing, should use letters instead, don't know if you are referring to the number or the index. Didn't even show duplicate case.
@BackToBackSWE5 жыл бұрын
yeah u rite
@kewtomrao4 жыл бұрын
Dont we need two for loops(i mean nested) to get the occerences?
@BackToBackSWE4 жыл бұрын
I don't remember the code for this to be honest
@annonime11025 жыл бұрын
Good video and thanks for that. But wish you had used a better example. Array of size 5, indices 0-4, array values 0-4. Simply too confusing and required several iterations to get it.
@BackToBackSWE5 жыл бұрын
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
@evalyly93134 жыл бұрын
This is a very good video. However, if the example is an array with duplicates, it would be better. Thanks
@BackToBackSWE4 жыл бұрын
yes
@cristinachung1523 жыл бұрын
I love your videos! I'm taking algorithm design course and you explain things better than my prof lol
@akashjain29907 ай бұрын
Why do you need to traverse backwards for placement?
@KaaiSpeaksHisMind5 жыл бұрын
I think you should have explained the algorithm further by showing why exactly (after performing the accumulative 'running sum') does each index denote the last possible occurrence of value (i). Great video nonetheless, thank you!
@BackToBackSWE5 жыл бұрын
yeah, you're right
@bassemsamuel32499 ай бұрын
Thankss a lot for this explanation really clicked for me!
@paveldubinin5154 жыл бұрын
Great explanation, but I with you'd use different test set as an example, it does not show how algorithm behaves in case of duplicates.
@BackToBackSWE4 жыл бұрын
yes
@supamdeepbains51724 жыл бұрын
homie can u drop new videos on Rod cutting dynamic programming etc.
@BackToBackSWE4 жыл бұрын
I don't want to
@supamdeepbains51724 жыл бұрын
Back To Back SWE not fair dawg
@jasonb41173 жыл бұрын
Why do you start from the last item in the array instead of the first item for the final loop?
@bob_jones5 жыл бұрын
"At the end of this, we are going to generalize this to mapping anything to an integer." Where is this done?
@BackToBackSWE5 жыл бұрын
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.
@mahmoudeslami11452 жыл бұрын
I got it , I got it , I got it , I got it , Thanks 🔥
@zehrasubas97685 жыл бұрын
I'm confused on why we say n+k instead of n, because we know for sure k will be smaller or equal to n (worst case equal to n), in that case, shouldn't we ignore it?
@BackToBackSWE5 жыл бұрын
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".
@zehrasubas97685 жыл бұрын
@@BackToBackSWE Thanks a lot for the detailed reply!
@mdrsoooow2 жыл бұрын
dude i fucjiubng love you
@carolamarini6224 жыл бұрын
Great video! but I don't seem to find the code? Where is it?
@BackToBackSWE4 жыл бұрын
Repository is deprecated and no longer maintained
@shivnandantiwari74894 жыл бұрын
I don't skip your videos that's how I can help you and I suggest other to do this .... Thanks bro ... You are one of the best computer teacher
@BackToBackSWE4 жыл бұрын
sure
@shivnandantiwari74894 жыл бұрын
Thank you sir you replied it's a great pleasure to me
@arunm6195 жыл бұрын
Is there any particular reason as to why we are trying to find positions for our numbers in the given array from the last? We can do a normal traversal of the given array right? I'm talking about the last placement and decrement of count step.
@BackToBackSWE5 жыл бұрын
yeah we can
@arunm6195 жыл бұрын
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.
@BackToBackSWE5 жыл бұрын
@@arunm619 nice
@moonmaster363 жыл бұрын
But what if we do not get k
@joseardila14574 жыл бұрын
Hi, amazing video, but I have one question: for this init array => [ 0, 200, 5000] => k would be 3 or 5001?
@BackToBackSWE4 жыл бұрын
I don't remember to be honest, I'd have to recap on counting sort
@harlequin35333 жыл бұрын
I think it's 3, from how I understood it
@notyournormaldev14193 жыл бұрын
k would represent the range of nos so max - min +1 = 5001
@karamkassem98212 жыл бұрын
5001 , here counting sort is not efficient
@FilipeMmad5 жыл бұрын
Hi there! I've just found this video and its helping me a lot! But I have a doubt. If I don't know the size k of my count array is it still worth to use counting sort? I have an 10^6 numbers in my vector but I don't know their sizes.
@BackToBackSWE5 жыл бұрын
im not sure, I forgot counting sort since I shot this, I need a refresher
@bolu33074 жыл бұрын
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.)
@BackToBackSWE4 жыл бұрын
@@bolu3307 thanks
@peterraad234 жыл бұрын
Cant wait for you to hit 100k subscribers. You'll get it done in no time props to you man
@BackToBackSWE4 жыл бұрын
hey
@peterraad234 жыл бұрын
Back To Back SWE hey
@soulmusic65304 жыл бұрын
great video. been stuck on this for a long time
@BackToBackSWE4 жыл бұрын
Great to hear!
@kainguyen42594 жыл бұрын
Can you do a video on Radix Sort please?
@BackToBackSWE4 жыл бұрын
sure
@maryannegichohi70634 жыл бұрын
This video is amazing ,good explanation.
@BackToBackSWE4 жыл бұрын
sure
@shivarammuthukumaraswamy71644 жыл бұрын
TYSM
@BackToBackSWE4 жыл бұрын
ye
@imolafodor46673 жыл бұрын
i guess its important to emphasize that the mechanism is at is, because an element can also have multiple occurrences in the initial array.. then its important to have the intermediate running sum, starting from the back.. because the order needs to be maintained (FIFO), even if the numbers are the same
@polarbeargc74913 жыл бұрын
what about duplicate value in the array? I cannot figure it out with this algorithm.
@supamdeepbains51724 жыл бұрын
bro I cannot find selection sort on your channel? i remember you had it
@BackToBackSWE4 жыл бұрын
I think it is somewhere
@supamdeepbains51724 жыл бұрын
Back To Back SWE 😂. Oh okay I see how it is naowwwww 😂
@nevilholmes59002 жыл бұрын
thanks
@epiclasersharks1866 Жыл бұрын
hero
@saymyname69783 жыл бұрын
We go from back to make sure that the sorted array is stable. We are basically placing the last occurence of the element in the last possible index it can be placed at.
@i_am_reshad4 жыл бұрын
I am now at 3:56 . Everything still clear . Thanks
@i_am_reshad4 жыл бұрын
I am at 7:32 , and still understand everything
@BackToBackSWE4 жыл бұрын
ok
@BackToBackSWE4 жыл бұрын
ok
@renseragaki46374 жыл бұрын
15:45 the symbol looks like Baymax from Big Hero 6 lmao
@BackToBackSWE4 жыл бұрын
ok
@apoorvauppala36793 жыл бұрын
Can't believe it took me so long to find you. Your videos are the best.!!
@TheAmeer38814 жыл бұрын
Subbed. Thank you boss. Ur gono b a star
@BackToBackSWE4 жыл бұрын
sure
@guardofhonour30895 жыл бұрын
final array index can start from0/1
@BackToBackSWE5 жыл бұрын
nice
@zifanxu5223 жыл бұрын
Thanks so much for your videos to help me understand BFS and DFS, now you are my go to channel when I learn new algorithms
@100_swastiksanyal5 Жыл бұрын
You explain in a very smooth manner. Your videos are so soothing to watch. you are so calm
@plidjeezy25422 жыл бұрын
great explanation. easy to understand.
@atvonguyentien5726 Жыл бұрын
You know what? You're so good at teaching. Let keep the good work and your effort will definitely paid off sooner or later.
@BackToBackSWE Жыл бұрын
Appreciate that!
@butteredtequilla90462 жыл бұрын
Hi! I love your videos! Where exactly is the code you reference to be in the description? Is it in the website that is linked?
@BackToBackSWE2 жыл бұрын
You can check out the code repository on backtobackswe.com/
@lilit35522 жыл бұрын
You have a talent in teaching. I was so confused by watching other videos, your video was the easiest to understand.
@BackToBackSWE2 жыл бұрын
Happy to hear that!
@joedonald15564 жыл бұрын
Wow tHANKs!
@BackToBackSWE4 жыл бұрын
sure!
@jerryquid40572 жыл бұрын
brilliant explanation, thank you
@darod60984 жыл бұрын
Thank you.
@BackToBackSWE4 жыл бұрын
sure
@danizelikman16884 жыл бұрын
i gotta say this video is awesome i've seen a few videos and non of theme were this awesome
@BackToBackSWE4 жыл бұрын
thx
@skinzzs16992 жыл бұрын
I love your videos! Great explanation
@BackToBackSWE2 жыл бұрын
Thank you!
@drakezen5 жыл бұрын
Great explanation!
@BackToBackSWE5 жыл бұрын
thanks
@rohangarg54734 жыл бұрын
Thank you!
@BackToBackSWE4 жыл бұрын
ye
@ehsanhosseini58614 жыл бұрын
Your videos are awesome, great explanation. I Have a few questions not related to this video but for interview preparation. I already did about 70 leet code but after a month when I look at the same problem I solved it I don't remember which algorithm I used and it takes me 30 mins or one hour to solve it again. Is this normal? Can you please guide me in these 3 questions: 1. When were you looking at the correct solution -- before you began the problem when you got stuck, only after struggling to solve it yourself? How long until you would look at the solution, typically? 2. What would you do after you'd not solved the problem, but looked at the answer? 3. What would you do after you did solve a problem?
@BackToBackSWE4 жыл бұрын
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.
@walidbaroudi5464 жыл бұрын
2 arrays and cumulative summing for sorting simple integers is a bit of an overkill. it's good for keeping the sorting stable, but stability is meaningless when sorting integers. besides, since the elements are unique, counting is unnecessary, so the example is probably not the best (woulda been great for radix sort).