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!
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!
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 :)
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.
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.
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.
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...
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????
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 (
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...
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.
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! :)
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 ???
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.
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!
@@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.
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.
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
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.
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!
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.
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); }
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!
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!
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 :)
@@paramagurug9237 No that not possible as multiple set of characters might have sample total value. So in that case your grouping would go wrong.
Plz help me from were I can start competitive programming
Iam beginer suggest me good resourceses to start ds and algo
love your videos great work !!! thanks man !!
So happy to hear it, thanks so much for your support Arvind!!!
ohhh your recorded volume is low , and i was checking what happens to my earphones
same
it was so clean
understood like a story
wooo happy to hear that thanks for letting me know :)
Nice video and very well explained Kevin. Can you also please make a video explaining 73. Set Matrix Zeroes.
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.
Do you have a code for this? If yes please give me a link to see it.
@@sourin.majumdarit's in the neetcode video for this same problem. He explains this approach in detail
Interesting how checking if anagram for 2 strings vs checking for multiple strings has different approaches
Dammn man I have been watching your content for the past 2 months and you didn't disappoint me once.
Hatsoff 💯
Keep Doing This!
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.
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.
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.
Check the link in the description and thanks!
I got shocked. you're genius. I couldn't imagine to sort each string. really thanks.
Thanks Heewon and thanks for the support!
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
Beautiful
Dope! dope dope!
I wanted to know, is there any other solution that is more optimal than this??
You are so good !
Thank you
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)
God i remember when interviews were this simple pre-covid days, now we get asked DP for entry level roles
Hi @Kevin, Could you please tell me the space complexity of this algo?
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...
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;
}
you are awesomeeee!!
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????
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 (
I got this same example with ms interview.
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...
Kevin why on line 8 .tostring() doesn't work?
Nice Work
Excellent explanation and very straightforward to follow, although not the most efficient solution to this problem (O(MN) is possible)
No need to sort the characters. You can make your HashFunction in such a way that can eliminate character sorting.
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.
Nice 😀
Thanks Naveen!
hmmm I'm sure there is a way to do this using Java Streams...
someone please explain me after the "if statement" that kevin wrote ...
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! :)
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 ???
thank you
you got it
Why did you record in low volume :((
Komal Bhalge older vids on in lower volume cuz I didn’t realize but now the volume is better on more recent vids
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.
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!
@@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.
Please increase the volume 😅😅
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.
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
I'm pretty into hashtable now!!! Thanks Kevin! Voted!
wooo thanks Yi :)
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.
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!
@@KevinNaughtonJr Correct. For Eg : "ac" and "bb" would have the same sum (198) and hence would get hashed to the same value.
@@ambikaiyer29 Yeah that's what I was afraid of, super cool idea though, maybe there is another way to avoid sorting though somehow?
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.
@@nck87 Nice! Man...sometimes I wonder why I don't use Python for my interviews lol
can't really hear you
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.
class Solution {
public:
vector groupAnagrams(vector& strs) {
vector group;
unordered_map mp;
for(auto str: strs)
{
string sorted=str;
sort(sorted.begin(),sorted.end());
mp[sorted].push_back(str);
}
for(auto it=mp.begin();it!=mp.end();it++)
{
vector temp;
for(auto x: it->second)
temp.push_back(x);
group.push_back(temp);
}
return group;
}
};
Nice Video 😊
3:30
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);
}
I can't understand wtf is going on 🥲🥲🥲