Welcome back.
Now let's try to see how we can solve this question.
Now over here I have two anagrams car and Ark.
Ark.
Right.
You can see that the same letters are used for both these words and exactly the same number of times.
So these two are anagrams.
Now, if we just sort these letters, let's just sort these letters.
So if we sort the letters in car we will get a car.
Now let's sort the letters in Ark.
So if we do that again you can see we will get a car.
So if we have two anagrams and if we just sort them, you can see that we will get the same word right.
So we will try to make use of this property, this interesting observation to try to solve this question.
So let's say this is the array which is given to us.
And you can see that it has various strings in it.
Now let's write the indices of this array.
So we have 012345 and six.
So these are the indices.
Now let's create another array.
And in the the new array which you are creating over here is going to consist of these strings in the
sorted manner.
So we are going to take each string sorted and then put it into our new array.
So over here we have Ark.
Now when we sort this we will get a car.
So that's going to be at index zero.
And over here we have a b c.
When we sort this we will again get a b c and then c a r becomes a c r.
And we continue c a t will become act and act will remain as it is act itself and then a, c, b will
become a, B, C and ATC will become act.
So we have formed a new array, and each string in the original array is sorted and put into the new
array.
So this is our new array.
Now we can just use the property right.
We know that two anagrams, if they are sorted they will have they will look the same right.
For example we have a r c and we have c r.
So we have seen that example right.
So after sorting these we can see that over here in the sorted array these two are just the same.
So now we can just use a hash table.
And we will just iterate.
Or we will just go through the array which is given to us by having an index.
Right.
So we'll have I pointing to zero then one etc..
So we will iterate through the arrays, these two arrays together.
And then we will check if whatever is there in the sorted array is there in our hash table.
If it is not there, then we will use the value in the sorted array as the key, and we will use the
same, uh, the the value in the same index in the original array as the value.
And we will push it to our hash table.
And if we do that, we will be able to group all the anagrams together, because we know that the anagrams
will look the same when they are sorted.
So let's proceed.
So initially I is equal to zero.
So we are at index zero.
And over here we have ACR.
ACR is not there in our hash table.
So let's make an entry.
So the key is going to be ACR.
And the value is going to be an array with the value RC which is over here.
So let's do that over here.
All right.
Now we move to index one.
So at index one in the sorted array we have ABC.
And we see that ABC is not there in our hash table.
So we are going to insert the key value pair where the key is going to be ABC.
And the value is what we have in the original array which is ABC itself.
So let's go ahead and insert that.
And this is going to be an array.
So the value is going to be an array.
Now we proceed to index two.
At index two we have ACR over here.
And we see that ACR is already there in our hash table.
So we are going to push the value in the original array at index two which is car or car into this value
array over here.
So let's do that.
So we get car over here.
Now we move to index three.
So we have act.
Act is not there in our hash table.
So let's insert this as the key.
And the value is going to be cat.
So let's insert that over here.
All right.
And then we move to index four.
So at index four we have act and act.
So act is already there.
So we have the key.
So we're going to push this value into the the values array over here.
So let's do that.
So we get act over here.
Now we proceed to index five.
We have ABC as the key, and we see that ABC is already there in the hash table as a key.
So we're going to push the value ACB into this array over here.
So let's do that.
So we get ACB over here and then we move to I is equal to six.
So at this point the sorted array has the value act.
Act is already there in our hash table.
So we are going to push this value which is which is ATC into this array over here.
So let's do that.
So we get ATC over here.
All right.
So that's that's it.
So we have formed our hash table.
Now we just need to return these values right.
So we just need to return these values in an array.
So that's going to be the answer.
So you can see we have r c and c r as an array.
Then we have ABC and ACB.
So that's this array over here.
Then we have Cat Act and ATC as an array which is this array over here.
And that is our solution.
So we have grouped the anagrams together and then returned it as an array.
Now let's take a quick look at the time and space complexity of this solution.
Now for the time complexity to to analyze the time complexity, let's say that's is the number of strings
in the array which is given to us, which is this array over here.
And let's say that n is the maximum number of characters in a string.
All right.
So we are just taking the maximum number of characters because as you know, big O analysis just tries
to find out the upper bound of the time complexity.
Now to sort one of the strings, we will take n log n time, write n log n time complexity or operations.
Therefore, to sort s strings we are going to take s into n log n operations, or the time complexity
is going to be of the order of s into n log n.
Again, n log n is to sort each string right because n is the maximum number of characters.
So this is going to be the upper bound.
And then we have s strings.
So that's why we are multiplying this with s.
So the time complexity is o of s into n log n.
Now what about the space complexity.
Let's think of what all takes space.
And before that also after we go, after we loop through the um the array.
Right.
These two arrays, we are doing that after we are sorting them, we are looping through them.
Right.
So at that point we are just doing constant operations.
Again, we know that for looping through them, we are doing s operations because there are s strings,
but then s is less than s into n log n.
So we can just neglect this.
And then when we are looping through them we are doing just constant time operations like checking if
the value is there in a hash table and if not pushing.
So these are just constant time operations.
All right.
Now let's proceed to the space complexity.
Now what all takes up space that can scale right.
We are creating a sorted array over here.
So we can see that over here.
Then we have a hash table.
So that takes up space.
And then we have our output array.
So these are the three things that take up space over here.
Now the sorted array is going to take up space of the order of s into n.
Because again n is the maximum characters and s is the number of strings which is there in the array
which is given to us.
So this is the upper bound right s into n for the space that the sorted array can take up, right.
So that's again a constant into s into n.
And we are just neglecting the constant.
And the output array is also going to take up space of the order of s into n.
And the hash table also is going to have everything inside it.
Right.
So each of these elements is going to be there in the hash table.
And then we are have some more space taken up for the keys.
But again the space taken up is going to be of the order of s into n.
So that's why we can say that the space complexity of this solution is O of s into n.