As per usual, I forgot to mention time complexity...in my opinion, the time complexity would be O(nmlogm) where n is the max number of words we can receive in "strs" and m is the largest size a word in "strs" can be. Let me know what you guys think!
@dancitadel93
5 жыл бұрын
I think you are right, probably only good to mention that the O(mlogm) comes from the sorting, it is using a dual pivot quicksort under the hood and the O(n) is the regular iteration we are doing in all of the strings hence the O(nmlogm) time complexity. Great explanation Kevin!
@paramagurug9237
5 жыл бұрын
Can we calculate the ascii of each string (by converting each char to lower/ upper) and then map to same ascii integer value and store the list in the HashMap. You don't have to sort the string and do in O(n.m) - not sure about complexity but should be better than sorting to avoid mlogm :)
@prathamkesarkar
5 жыл бұрын
@@paramagurug9237 No that not possible as multiple set of characters might have sample total value. So in that case your grouping would go wrong.
@MariyamVlogs707
4 жыл бұрын
Plz help me from were I can start competitive programming
@MariyamVlogs707
4 жыл бұрын
Iam beginer suggest me good resourceses to start ds and algo
@dmitrykarpenko2271
5 жыл бұрын
Instead of sorting, you can use a dictionary of the following objects as a group key with custom equals() implementation: [{ key: letter, value: "letter count" }]. As we have constant number of letters in the alphabet, the time complexity will be linear at each step, not loglinear. Overall time complexity: O(MN), where N - words count, and M - max word length.
@sourin.majumdar
2 жыл бұрын
Do you have a code for this? If yes please give me a link to see it.
@prithvib8662
Жыл бұрын
@@sourin.majumdarit's in the neetcode video for this same problem. He explains this approach in detail
@naveenverma2390
5 жыл бұрын
ohhh your recorded volume is low , and i was checking what happens to my earphones
@darod6098
4 жыл бұрын
same
@free-palestine000
2 жыл бұрын
God i remember when interviews were this simple pre-covid days, now we get asked DP for entry level roles
@jlecampana
5 жыл бұрын
C++ version: vector groupAnagrams(vector& strs) { unordered_map m; for (auto s: strs) { string sorted = s; sort(sorted.begin(), sorted.end()); m[sorted].push_back(s); } vector grouped; for (auto &kv: m) { grouped.push_back(kv.second); } return grouped; }
@sourin.majumdar
2 жыл бұрын
Not a pro coder but here is my thinking about the SPACE COMPLEXITY: For the 2d arraylist which is being returned at the end sc would be O(n), coz it would contain all the strings which strs has. (Coz we do this in case of matrices so took the inspiration). For the hashmap, the worst case would be when all the given strings are not anagrams for any of the other, all are totally unique, so sc would become O(n). Therefore space complexity would be O(n). open to corrections tho...
@tanishktripathi8773
3 жыл бұрын
Dammn man I have been watching your content for the past 2 months and you didn't disappoint me once. Hatsoff 💯 Keep Doing This!
@prithvib8662
Жыл бұрын
Excellent explanation and very straightforward to follow, although not the most efficient solution to this problem (O(MN) is possible)
@sourin.majumdar
2 жыл бұрын
String sorted = new String(characters) WORKS But String sorted = characters.toString() DOES NOT If I do the latter, the anagrams don't get grouped, basically we get wrong output. WHY ???
@heewonjeong2158
4 жыл бұрын
I got shocked. you're genius. I couldn't imagine to sort each string. really thanks.
@KevinNaughtonJr
4 жыл бұрын
Thanks Heewon and thanks for the support!
@akaakaakaak5779
4 жыл бұрын
I don't even need to watch the video now, read your comment and now I'm kicking myself. I knew it had to be easier
@treyquattro
4 жыл бұрын
would not have used sort; would have manually counted chars in 26-element array then reconstituted key from frequencies. Your solution, as usual, much more elegant and straightforward, and likely quicker for short strings (
@galanoth17
2 жыл бұрын
I was thinking of having a HashMap of Char to Count. Then I would create one such Hashmap for each string. Then I would compare the Hashmap using Map.equals method. And if two hashmaps are equal then they are anagrams, otherwise they aren't. So if two are equal then I would put them strings that generated those hashmaps into a list. Not sure whether that has better time complexity or not because I don't know what the time complexity is for comparing Hashmaps. Actually I can calculate it. Creating hashmaps is O(n) and then comparing two Hashmaps is also O(n). So I guess the time complexity is O(n * m) where n is the length of the longest string and m is the number of strings given. I think for your solution the time complexity would be O(nlgn * m) where n is the length of the longest string and m is the number of strings given.
@rahulshrivastava3040
5 жыл бұрын
Could you tell me what is the background music at the starting of every video? I am just curious. And Kudos on the videos. You explain it very well.
@KevinNaughtonJr
5 жыл бұрын
Check the link in the description and thanks!
@lifeofme3172
4 жыл бұрын
There is a small correction int the above code, the sorted also needs to be added as value to map when it's added as key. Else the output does not contain the sorted value.
@sourin.majumdar
2 жыл бұрын
The sorted string has been used as the key, and all the strings which upon sorting looks like a specific key gets mapped to that sorted string as a value. coz we need to return the value set of the map. Say the sorted string is also there as an anagram then automatically it will be mapped to to its sorted form i.e. to itself. So definitely we will be returning the sorted one also coz IT WAS IN THE INPUT.
@newanurag
2 жыл бұрын
No need to sort the characters. You can make your HashFunction in such a way that can eliminate character sorting.
@nani4027
3 жыл бұрын
I wanted to know, is there any other solution that is more optimal than this??
@vk1618
4 жыл бұрын
Interesting how checking if anagram for 2 strings vs checking for multiple strings has different approaches
@mubasherusman3943
4 жыл бұрын
Which complexity is better , O(n.m) where n is word array length and m is character length vs the your proposed O(n.m log m)
@LintaSheelkumar
3 жыл бұрын
Hi @Kevin, Could you please tell me the space complexity of this algo?
@sourin.majumdar
2 жыл бұрын
Not a pro coder but here is my thinking, For the 2d arraylist which is being returned at the end sc would be O(n), coz it would contain all the strings which strs has. (Coz we do this in case of matrices so took the inspiration). For the hashmap, the worst case would be when all the given strings are not anagrams for any of the other, all are totally unique, so sc would become O(n). Therefore space complexity would be O(n). open to corrections tho...
@nishant2narula
5 жыл бұрын
Nice video and very well explained Kevin. Can you also please make a video explaining 73. Set Matrix Zeroes.
@raulcalvomartin2979
4 жыл бұрын
I got this same example with ms interview.
@chintalapativenkataramarahul
3 жыл бұрын
Thank you
@saugatgarwa6389
4 жыл бұрын
it was so clean understood like a story
@KevinNaughtonJr
4 жыл бұрын
wooo happy to hear that thanks for letting me know :)
@komalbhalge5119
4 жыл бұрын
Why did you record in low volume :((
@KevinNaughtonJr
4 жыл бұрын
Komal Bhalge older vids on in lower volume cuz I didn’t realize but now the volume is better on more recent vids
@nealpatel7696
5 жыл бұрын
I don't know why I just realized this but you always submit instead of running the code first. Any reason why? Or do you just know your answer is right? Another observation is that you stopped saying the time complexity although in this case, it's pretty trivial.
@KevinNaughtonJr
5 жыл бұрын
I've solved these problems before so I expect the code to pass. Yeah I forgot time complexity again :( it would be O(nmlogm) in my opinion where n is the total number of words we're given and m is the max size a word can be
@rushabhjaiswal1442
5 жыл бұрын
Hey kevin can you please tell how you adding the first string into the hash map because we are sorting the first string and after checking it with hash map, it it does not contain adding it to hash map with empty array list so how are we adding that first one????
@mohakchaudhary1981
5 жыл бұрын
Please increase the volume 😅😅
@abhirupdas719
3 жыл бұрын
You are so good !
@nck87
5 жыл бұрын
You should just convert each char to its integer value, add them up - that will be a unique hash that will always map to its grouped anagrams and avoid the sorting cost - nlogn in most common algos.
@KevinNaughtonJr
5 жыл бұрын
Love that idea, but isn't it possible that you could have a word that let's say has one character whose "unique" hash (aka sum of all characters) is 40 and then some other word, let's say with 2 characters that together sum to 40 causing a collision (i.e. saying two words are anagrams when they're not)? LMK your thoughts!
@ambikaiyer29
5 жыл бұрын
@@KevinNaughtonJr Correct. For Eg : "ac" and "bb" would have the same sum (198) and hence would get hashed to the same value.
@KevinNaughtonJr
5 жыл бұрын
@@ambikaiyer29 Yeah that's what I was afraid of, super cool idea though, maybe there is another way to avoid sorting though somehow?
@nck87
5 жыл бұрын
Ah you are right - i didn't account for duplicates. i think in that case we could just keep the count of seen alphabets in a list and use that as the key to our map. here is the python version of the solution: def groupAnagrams(self, strs): hmap = {} for mstr in strs: tt = [0]*26 for ss in mstr: v = ord(ss) -97 tt[v] +=1 hmap.setdefault(tuple(tt), list()).append(mstr) return hmap.values() this would still be o(NM) time complexity.
@KevinNaughtonJr
5 жыл бұрын
@@nck87 Nice! Man...sometimes I wonder why I don't use Python for my interviews lol
@ArvindVerma-ct7oq
5 жыл бұрын
love your videos great work !!! thanks man !!
@KevinNaughtonJr
5 жыл бұрын
So happy to hear it, thanks so much for your support Arvind!!!
@sameepdatta863
4 жыл бұрын
Kevin why on line 8 .tostring() doesn't work?
@SonnyLando
4 жыл бұрын
hmmm I'm sure there is a way to do this using Java Streams...
@eshanikabhattacharjee383
3 жыл бұрын
you are awesomeeee!!
@TheMcallist1
5 жыл бұрын
Beautiful
@jlecampana
5 жыл бұрын
Hello Kevin, first I would like to congratulate you for making these videos, they're really helpful and well explained. Secondly, I was wondering if you could share with me what resources you think are the best to understand Dynamic Programming? What did you personally use when you were a beginner? Thanks so much.
@KevinNaughtonJr
5 жыл бұрын
Thanks so much I'm happy to hear you're finding my videos helpful! For DP, I would suggest to start you look at a simple problem that is solved "top down" and understand that when a problem is solving using top down processing it's really just using recursion but never solving any sub problem twice. I'm hoping to make a video on explaining DP in depth soon!
@jlecampana
5 жыл бұрын
@@KevinNaughtonJr Well, I've done a few and understand/can solve the classics like: KnapSack, LCS, LIS, Max SubArray Sum, Coin Change, Rod-cutting. But there are some DP problems that have really broken my spirit, for example: LeetCode #276 - Paint Fence which is labelled as "Easy" or #152, both of them appear to be easy on the surface but it's like there's always "a Catch" or a trick in order to Formulate the Recurring Relation. And that's the thing, I believe any DP problem is solvable as long as you figure out the Recurrence Relation, but If you can't, you're done. I'm not sure how to get better.
@bigray712
5 жыл бұрын
not efficient though, takes 0(n) for going through array and slog(s) for sorting ---> resulting in n*s*log(s). that's almost bruteforce.
@thesoftwareengineer17
2 жыл бұрын
Nice Work
@BullishBuddy
5 жыл бұрын
Dope! dope dope!
@naveens5809
5 жыл бұрын
Nice 😀
@KevinNaughtonJr
5 жыл бұрын
Thanks Naveen!
@surabhipriya8386
4 жыл бұрын
someone please explain me after the "if statement" that kevin wrote ...
@Vidur11
4 жыл бұрын
The if condition is basically checking if the map contains the key element or not. In this particular example, he's saying that if the map doesnt contain the key, then add it to the map(map.put(sorted,new ArrayList()). Then the next statements finds the new key he just added, and pushes the original unsorted string into the arraylist, thus creating a new key-value pair. Hope this helps! :)
@shivamd23
3 жыл бұрын
Nice Video 😊
@yongfulu8984
3 жыл бұрын
can't really hear you
@yicai7
4 жыл бұрын
I'm pretty into hashtable now!!! Thanks Kevin! Voted!
Missed out this part -----> if(!map.containsKey(sorted)){ List list = new ArrayList(); list.add(curr); map.put(sorted, list); }else{ map.get(sorted).add(curr); }
Пікірлер: 82