Welcome back.
Let's now go ahead and code the solution which we discussed in the previous video.
So we are going to write a function which will take in an array of strings.
And then it will group the anagrams together and then return it as an array of arrays.
This is what you're going to do.
So let's go ahead and write the function.
Let's call this function group anagram.
Anagrams.
All right.
Now this function is going to take in the array of strings.
So let's just call this array strings itself.
Now inside the function we are going to first create another array which is going to be the strings
sorted right.
So let's say sorted const sorted is equal to strings which is this array which is passed to the function
over here dot map.
So we are going to go through each element in the strings array.
And then we are taking each element and we will just split it up.
So x dot split.
And after we split it up we are going to sort the string.
So dot sort.
And after we have sorted the various characters, we're going to join them together and make it back
to a string.
All right.
So this is going to be the array where the strings are sorted.
Now we're going to have a hash table.
So let's just call it h t.
And this is going to be empty at the beginning.
So this hash table is empty.
Now we will just loop or iterate through the strings array which is given to us.
So for let I is equal to zero I less than strings dot length I plus plus.
And we will check whether that particular, um, string in the sorted array is there in the hash table
or not.
If it is not there, then we will take the value in the strings array at the same index, and then we
will insert that as the first value for the key.
So again remember the key is going to be from this array.
And the value is going to be from the strings array.
So let's just write that over here.
So the key or the hash table.
So this is for the hash table.
The key is going to be from the sorted array.
And the values are going to be from the strings array.
All right.
So that's what you're doing.
So let's go ahead and implement this.
So if not.
Hash table.
At.
Sorted.
At I.
So that is if the string in the sorted array at index I is not there in the hash table, then we are
going to say hash table at sorted at I.
Is equal to an array with the value strings at I.
Right.
So this is what we're doing over here.
Remember the key is coming from the sorted array.
And the value over here is coming from the strings array.
Now if it is there so else that is we already have an entry in the hash table where the key is what
we have in the sorted array at index I.
In that case we are going to push to that particular array.
So that's the value is an array right.
So to that array we are going to push strings at I.
So we can say hash table at sorted.
At I.
Dot push.
And we are pushing strings at I.
So this is going to be pushed to that array.
The value array.
All right.
Now once we are out of this for loop we have we are done with building our hash table.
Now we just have to return the values in our hash table.
And remember every value is an array.
So we can just return object.
Dot values.
And then we pass in the hash table.
That's it.
So this is our function.
Now let's go ahead and test our function.
We're going to pass an array of strings.
So let's just define that over here.
So let's say strings is equal to and we can have the strings eat.
Then we can have tea.
Then maybe we can have ten.
And we can have at.
And then we can have Natty.
And let's have bat.
And we can have tab.
All right.
So these are the strings in this array.
Now let's call the function group anagrams.
And let's pass this array over here to it.
And let's run our function and let's see what we are getting.
So you can see we have three groups over here.
Now let's just walk through the groups and see whether this is working.
Correct.
So let's just grab a pen.
All right.
So over here we have e a t so you can see that's over here.
Then we have t we can see that these are anagrams right.
So we have t over here as well.
Then we have t a n t a n is over here.
And then we have a t a t is part of this one over here.
So yes that's also an anagram with t and e a t eat.
And then we have nat Nat and tan.
These are anagrams.
So yes they are grouped together correctly.
And then we have bat over here and we have tab over here which are grouped correctly.
So yes our function is working and it has identified the anagrams and group them together.
Now let's just walk through the code and see what's happening over here.
Now again the input over here is this, uh, string, the string, the array with strings over here.
Now let's let's see what's happening.
So we are calling group anagrams, and we are passing this array to the function over here.
And once inside the function we are creating our sorted array.
So let's write our sorted array over here.
So this is going to take each element from the strings array.
So we are using the dot map operator.
So we are taking each element and we are splitting it sorting it and joining it back.
Right.
So this over here becomes a e t and this becomes a e t tan becomes a n t.
And at this becomes eight again.
And then Nat, this becomes a NT and then bat, this becomes a bt and tab also becomes a bt.
So this is our sorted array.
So that's at this line of code.
And then we have our hash table over here which is empty.
So let's just write that over here.
So the hash table at this point is empty.
And then we are going to have this for loop and we are iterating through the strings, which is this
array over here.
So I is going to take the values from zero, one, two, three, four, five and six.
So again let's write that over here 0123, four five and six.
Now when I is equal to zero we are checking is the value in sorted at I which is at.
Is it there in our hash table.
No it's not there.
So we're going to say the key is at and the value is going to be an array with strings at I which is
e at.
All right.
So let's continue.
And then we come to index one.
So at this point we have eight over here which is already there right.
So again we see that it's there.
So we come over here and to this array we're going to push strings at I which is T.
So this is added over here.
And we go to index two and we have a and over here we see that it's not there.
So we inserted a and T is the key.
And the value is going to be t a n.
Right.
So that's an array with t a n.
So that is what we're doing over here.
And then we go ahead to I is equal to three.
And we have at E and at three we have at.
So this is already there.
So we're going to push at E to this array.
So we are adding a T over here.
And then we go to the next index.
And we have Nat.
And over here we have a and T a and t is already there in our hash table.
So we come to this else part over here and to this array.
We are going to push Nat.
So we get Nat also over here.
And then again we go to I is equal to five.
We have b a t.
And over here we have abt.
Abt is not there in our hash table.
So we're going to insert it right.
So abt and the value is going to be an array with b a t as the value.
So that's happening over here at this line of code.
And we go to I is equal to six.
So at this point we have abt over here which is already there.
So we come to this line of code and we are going to push to this array the value over here which is
t a b.
So to b is also inserted over here.
And then we come out of the for loop.
Because now I become seven.
And seven is not less than seven right.
So we come out and then we are just going to return the values of the hash table which is this part
over here.
So we're going to return these three arrays as an array.
All right.
So there's the first element in the array which has eight t and eight.
Right.
And similarly the second array in this array is going to have tan and nat.
And the third array is going to have bat and tab.
So this is how we have solved this question.
Now let's take a quick look at the space and time complexity of this solution.
For this let's say that n is the maximum characters in any string over here.
So this is the maximum characters.
So because we can have strings of different length, even though over here everything is of length three,
we could have strings of different length.
And let's be the number of strings.
For example, over here we have we have seven strings.
So s is the number of strings.
All right.
So over here you can see we are doing sorting on each of these strings.
Right.
So this is going to be n log n for each string.
We are just taking an upper bound.
So n is the maximum character.
So we can just take n log n as the upper bound of the number of operations to be done, to sort a particular
string and to sort all the strings, that is, to sort s strings, we have to do s into n log n operations.
And then we have this for loop over here.
In this for loop we are going to do s iterations because this is zero from zero till less than strings
dot length.
Right.
So and then we have seen over here's is the number of strings.
So over here we are doing s operations.
And then we are just returning this right.
So that's it.
So again whatever we are doing inside this is just constant time operations.
We are checking if something is there in a hash table.
And if not we are inserting.
So these are just constant time operations.
So we can say that the time complexity is s into n log n plus s.
Now s into n log n is greater than s.
So we can say that the time complexity is just o of s into n log n.
Now, what about the space complexity?
Now, what are the things that take up space?
We have this new array which we are creating.
So that takes up space.
And then we have this hash table.
So that also takes up space right.
So what about this array.
So over here let's again take this n is the maximum characters in a particular string and s is the total
number of strings.
Then we can say that the sorted array is going to take up space of the order of n into s.
Again we are just taking an upper bound, right?
So that's why we are doing n into s, even though it may not be the case that every string has n characters,
and the hash table is also going to have every element inside it.
So this also is going to take up space of the order of n into s.
So we can see that the space which is used is also of the order of n into s.
So the space complexity is O of n into s.
And we can also notice that there's one more thing that takes up space, right?
We have this output array.
This also is going to take up n into s space right.
So again the space complexity of this solution is O of n into s.