Group Anagrams (LeetCode 49) | Full solution with 2 methods and examples

Group Anagrams (LeetCode 49) | Full solution with 2 methods and examples | Study Algorithms

Рет қаралды 25,541

Күн бұрын

To see more videos like this, you can buy me a coffee: www.buymeacoffee.com/studyalg...
You are given an array of strings, you need to group the anagrams. Two strings are said to be anagrams if they have the exact same characters with the same frequency. The placement can change though. Watch this video to learn 2 methods to solve this problem. We will take advantage of properties of anagrams and use it in our favor. At the end we will see a dry-run of the code to see what is actually happening behind the scenes.
00:00 - Intro
01:12 - Problem statement and description
04:40 - Method 1: Categorize by Sorting
09:03 - Method 2: Categorize by Frequency
13:09 - Dry-run of Code
15:44 - Generate Frequency String
18:09 - Final Thoughts
📚 Links to topics I talk about in the video:
Brute Force Algorithm: • Brute Force algorithms...
Sorting Techniques: • Sorting Techniques
Time Complexity: • What is the Time Compl...
What is Big O?: • Big O Notation Simplif...
📘 A text based explanation is available at: studyalgorithms.com/string/le...
Code on Github: github.com/nikoo28/java-solut...
Test-cases on Github: github.com/nikoo28/java-solut...
📖 Reference Books:
Starting Learn to Code: amzn.to/36pU0JO
Favorite book to learn algorithms: amzn.to/39w3YLS
Favorite book for data structures: amzn.to/3oAVBTk
Get started for interview preparation: amzn.to/39ysbkJ
My Recording Gear:
Recording Light: amzn.to/3pAqh8O
Microphone: amzn.to/2MCX7qU
Recording Camera: amzn.to/3alg9Ky
Tablet to sketch and draw: amzn.to/3pM6Bi4
💻 Get Social 💻
Follow on Facebook at: / studyalgos
Follow on Twitter at: / studyalgorithms
Follow on Tumblr at: / studyalgos
Subscribe to RSS feeds: studyalgorithms.com/feed/
Join fan mail: eepurl.com/g9Dadv
#leetcode #programming #interview

Пікірлер: 49

@dhavalchaudhary1786 3 ай бұрын

I generally not hit like on youtube videos, but this guy nailed it. Thanks for your community contribution NIkhil.

@WhosShamouz 9 ай бұрын

I was missing ONE idea and it popped in my head when I saw your first method, amazing explanation!

@devprakash5320 3 жыл бұрын

loved your explanation . But 1 thing I would like to correct . The time complexity of method 1 will be O(n k log k ) , where k is the length of the string , n is total strings . This is because sorting a string would take (k log k ) . Any way awesome explanation . thanks

@hersheynohara5887 Жыл бұрын

That's an amazing explanation! 👏👏

@amitbhattacharya356 2 жыл бұрын

I got really surprised by so a vivid and clear explanation. I appreciate your efforts.

@nikoo28 2 жыл бұрын

Glad I could help you out 😄

@yusufnurwahid898 Ай бұрын

Very clear explanation! Keep up!!! 👍🏻

@ramsidh2218 2 жыл бұрын

great explanation with animation step by step

@cuteangel1726 Жыл бұрын

Appreciate your effort !!!

@cricworld5806 Жыл бұрын

sir awesome explanation ...................

@user-ry5ge2dg7p 2 ай бұрын

great video and best ever explaination ever

@ricardohernandezmendez4207 2 ай бұрын

At the beginning it was difficult to find out how to solve this problem, but with this explanation it make it easy to solve it. Thank.

@Donkle365 2 жыл бұрын

Hey, I found this video trough the article and thank you for all the work, it really helped me. The solution of method 2 at line 34 has a mistake: "freq++;", you can't ++ an array, so we need to do freq[c - 'a']++ :)

@mujeebbridgetown 2 жыл бұрын

Nice explanation

@abhishekshankar6305 10 ай бұрын

you are the best

@hazerasarker2442 9 ай бұрын

Thank you Nikhil :D

@shaileshsathe9779 Жыл бұрын

Very well explained the techniques, code and dry-run. Great work Nikhil.

@shaileshsathe9779 Жыл бұрын

I don't know why, I ran both techniques sorting and frequency but sorting is showing less time than frequency method. sorting => 15ms frequency = 29ms. I believe its random.

@aryamiraozdemir Жыл бұрын

@@shaileshsathe9779 I'm not sure but I think it might be because frequency string has to be sorted so it takes even longer to count everything and sort the letters alphabetically

@plutomessi21 Жыл бұрын

Dhanyavad bhaiya, you are the best teacher I have seen on youtube😭

@nikoo28 Жыл бұрын

So nice of you

@yfchina143 4 ай бұрын

this there any better way for a frequency string algothrim?

@akshanshsharma8157 4 ай бұрын

In the sorting way, the time complexity is not O(nlogk) but rather O(n.klogk)

@sysybaba420 9 ай бұрын

Great video as usual thanks for this! PS its not pronounced vo-i-la but just vo-la, hope this helps!

@Vishal-8995 7 ай бұрын

Premium Explanation

@nikoo28 7 ай бұрын

🤘🏻

@mazthespaz1 Ай бұрын

i'm new to python and this was my solution def smash(str): tmp = 1 orda = ord('A')-1 ls = len(str) for i in range( ls ): tmp = tmp * (ord(str[i]) - orda) return tmp def groop(wordlist): grope = {} for word in wordlist: hashy = smash(word) if hashy not in grope: grope[hashy] = [] grope[hashy].append(word) return [val for val in grope.values()] if __name__ == '__main__': # arr = [ 'cat','tea','tan','ate','nat','bat' ] arr = [ 'eat','cars','tea','scar','a','listen','silent'] print (groop(arr))

@mazthespaz1 Ай бұрын

this solution worked in codewars but not leetcode. i need to refine the smash function to prevent duplicate hashes

@fourieruddin871 11 ай бұрын

Best

@abinashpanda393 7 ай бұрын

This might not pass all test cases, you have to add a delimiter like '#' while concatenating numbers in freq variable.

@nikoo28 6 ай бұрын

passes all cases on Leetcode as per the problem constraints. If you have different strings patterns, it might need a little tweaking.

@abinashpanda393 6 ай бұрын

@@nikoo28 You are right for ["bdddddddddd","bbbbbbbbbbc"] this will not going to pass. Probably new test cases have been added. Thank you for your response. Your tutorials are really helpful.

@jst8922 7 ай бұрын

8:14 should be "nat", not sorted string "ant". Otherwise your tutorials are the best regarding leetcode problems, because you explain with examples what should the code do.

@devansh_4u Жыл бұрын

beats 30% java codes, wonder what could be a better solution!

@nikoo28 Жыл бұрын

If you are concerned about having an overall faster solution, C++ should be the preferred language. Even with Java you can leverage some sort of caching and pre-processing of some results to obtain faster solutions. Generally not needed.

@devansh_4u Жыл бұрын

@@nikoo28 thanks sir

@sayanmanna2511 7 ай бұрын

But why light theme?? I am blind now..

@nikoo28 7 ай бұрын

Light is easier for diagrams and animations. Will keep using light theme.

@yogeshganpule2695 26 күн бұрын

tried watching but you just explained what the code does and its too confusing for me to undertsand what for each freq [c -'a']++; Does

@nikoo28 26 күн бұрын

c is the actual character…let us say it is character ‘k’ And we do c - ‘a’ What happens internally is both are converted to ascii Small ‘a’ has ascii 97 The character ‘k’ has ascii 107 So when you do c - ‘a’ we get 107-97 = 10 That means freq[10] This represents 11th character as array is 0 based indexing Means we are referring to frequency of 11th character in the English alphabet which is letter ‘k’

@yogeshganpule2695 24 күн бұрын

@@nikoo28 Thanks .

@himadripaul7332 Жыл бұрын

Excellent ... But disheartened to see less subscribers ... ☹️😑🙂

@nikoo28 Жыл бұрын

Yea…I don’t understand why my channel does not show up in results and suggestions. I have been doing everything possible: video descriptions, links etc.

@shaileshsathe9779 Жыл бұрын

@@nikoo28 You can add keywords like Leetcode, Anagram, Interview Prep just like you added for String.Maybe it will work

@boomshakalaka8567 2 жыл бұрын

There's nothing correct about this video. Lol. Indian programmers lulz

@nikoo28 2 жыл бұрын

did you find some problem in the explanation or the method? Always up for improvement...

@Sarvy001 2 жыл бұрын

@@nikoo28 I have found another solution here. Not explained in detail as you have done, but this one has less lines of code. kzfaq.info/get/bejne/nKd6pKSfqr3VYKM.html&ab_channel=ThatIndianCoder

@Nishi-Tiwari Жыл бұрын

@@nikoo28 You are best!