1
00:00:00,550 --> 00:00:01,480
Welcome back.

2
00:00:01,480 --> 00:00:05,740
Let's now go ahead and code the solution which we discussed in the previous video.

3
00:00:05,740 --> 00:00:09,550
So we are going to write a function which will take in an array of strings.

4
00:00:09,550 --> 00:00:14,020
And then it will group the anagrams together and then return it as an array of arrays.

5
00:00:14,020 --> 00:00:15,370
This is what you're going to do.

6
00:00:15,370 --> 00:00:17,050
So let's go ahead and write the function.

7
00:00:17,050 --> 00:00:19,420
Let's call this function group anagram.

8
00:00:21,220 --> 00:00:21,820
Anagrams.

9
00:00:21,850 --> 00:00:22,240
All right.

10
00:00:22,270 --> 00:00:25,570
Now this function is going to take in the array of strings.

11
00:00:25,570 --> 00:00:27,940
So let's just call this array strings itself.

12
00:00:28,390 --> 00:00:34,300
Now inside the function we are going to first create another array which is going to be the strings

13
00:00:34,300 --> 00:00:34,960
sorted right.

14
00:00:34,960 --> 00:00:42,460
So let's say sorted const sorted is equal to strings which is this array which is passed to the function

15
00:00:42,460 --> 00:00:44,140
over here dot map.

16
00:00:44,230 --> 00:00:48,490
So we are going to go through each element in the strings array.

17
00:00:49,090 --> 00:00:52,930
And then we are taking each element and we will just split it up.

18
00:00:52,930 --> 00:00:54,520
So x dot split.

19
00:00:56,860 --> 00:01:00,160
And after we split it up we are going to sort the string.

20
00:01:00,160 --> 00:01:01,270
So dot sort.

21
00:01:03,040 --> 00:01:08,020
And after we have sorted the various characters, we're going to join them together and make it back

22
00:01:08,020 --> 00:01:08,830
to a string.

23
00:01:10,580 --> 00:01:10,970
All right.

24
00:01:10,970 --> 00:01:14,570
So this is going to be the array where the strings are sorted.

25
00:01:14,570 --> 00:01:16,370
Now we're going to have a hash table.

26
00:01:16,370 --> 00:01:17,660
So let's just call it h t.

27
00:01:17,750 --> 00:01:20,030
And this is going to be empty at the beginning.

28
00:01:20,030 --> 00:01:22,460
So this hash table is empty.

29
00:01:22,610 --> 00:01:27,050
Now we will just loop or iterate through the strings array which is given to us.

30
00:01:27,050 --> 00:01:34,670
So for let I is equal to zero I less than strings dot length I plus plus.

31
00:01:35,550 --> 00:01:43,740
And we will check whether that particular, um, string in the sorted array is there in the hash table

32
00:01:43,740 --> 00:01:44,340
or not.

33
00:01:44,370 --> 00:01:50,520
If it is not there, then we will take the value in the strings array at the same index, and then we

34
00:01:50,520 --> 00:01:53,310
will insert that as the first value for the key.

35
00:01:53,340 --> 00:01:56,340
So again remember the key is going to be from this array.

36
00:01:57,580 --> 00:02:00,460
And the value is going to be from the strings array.

37
00:02:00,460 --> 00:02:01,900
So let's just write that over here.

38
00:02:01,930 --> 00:02:04,810
So the key or the hash table.

39
00:02:04,810 --> 00:02:06,280
So this is for the hash table.

40
00:02:08,350 --> 00:02:12,400
The key is going to be from the sorted array.

41
00:02:13,690 --> 00:02:17,230
And the values are going to be from the strings array.

42
00:02:18,470 --> 00:02:18,710
All right.

43
00:02:18,710 --> 00:02:19,700
So that's what you're doing.

44
00:02:19,700 --> 00:02:21,350
So let's go ahead and implement this.

45
00:02:21,350 --> 00:02:23,330
So if not.

46
00:02:23,930 --> 00:02:24,950
Hash table.

47
00:02:26,090 --> 00:02:26,480
At.

48
00:02:26,480 --> 00:02:27,500
Sorted.

49
00:02:28,250 --> 00:02:29,000
At I.

50
00:02:29,540 --> 00:02:36,710
So that is if the string in the sorted array at index I is not there in the hash table, then we are

51
00:02:36,710 --> 00:02:40,700
going to say hash table at sorted at I.

52
00:02:42,740 --> 00:02:46,520
Is equal to an array with the value strings at I.

53
00:02:48,340 --> 00:02:48,880
Right.

54
00:02:48,880 --> 00:02:50,140
So this is what we're doing over here.

55
00:02:50,140 --> 00:02:52,810
Remember the key is coming from the sorted array.

56
00:02:52,810 --> 00:02:55,570
And the value over here is coming from the strings array.

57
00:02:55,600 --> 00:03:01,600
Now if it is there so else that is we already have an entry in the hash table where the key is what

58
00:03:01,600 --> 00:03:03,730
we have in the sorted array at index I.

59
00:03:03,730 --> 00:03:07,000
In that case we are going to push to that particular array.

60
00:03:07,000 --> 00:03:08,650
So that's the value is an array right.

61
00:03:08,650 --> 00:03:12,370
So to that array we are going to push strings at I.

62
00:03:12,400 --> 00:03:15,760
So we can say hash table at sorted.

63
00:03:17,170 --> 00:03:17,950
At I.

64
00:03:19,780 --> 00:03:20,860
Dot push.

65
00:03:22,710 --> 00:03:24,450
And we are pushing strings at I.

66
00:03:24,450 --> 00:03:27,090
So this is going to be pushed to that array.

67
00:03:27,480 --> 00:03:28,470
The value array.

68
00:03:28,500 --> 00:03:29,190
All right.

69
00:03:29,220 --> 00:03:35,010
Now once we are out of this for loop we have we are done with building our hash table.

70
00:03:35,010 --> 00:03:38,430
Now we just have to return the values in our hash table.

71
00:03:38,430 --> 00:03:40,080
And remember every value is an array.

72
00:03:40,080 --> 00:03:42,480
So we can just return object.

73
00:03:44,100 --> 00:03:46,170
Dot values.

74
00:03:47,020 --> 00:03:49,030
And then we pass in the hash table.

75
00:03:49,450 --> 00:03:49,930
That's it.

76
00:03:49,930 --> 00:03:51,400
So this is our function.

77
00:03:51,400 --> 00:03:53,650
Now let's go ahead and test our function.

78
00:03:53,650 --> 00:03:55,360
We're going to pass an array of strings.

79
00:03:55,360 --> 00:03:57,190
So let's just define that over here.

80
00:03:57,190 --> 00:04:01,870
So let's say strings is equal to and we can have the strings eat.

81
00:04:01,870 --> 00:04:03,370
Then we can have tea.

82
00:04:04,060 --> 00:04:06,160
Then maybe we can have ten.

83
00:04:07,480 --> 00:04:09,820
And we can have at.

84
00:04:11,110 --> 00:04:13,390
And then we can have Natty.

85
00:04:14,560 --> 00:04:16,210
And let's have bat.

86
00:04:18,800 --> 00:04:20,540
And we can have tab.

87
00:04:22,630 --> 00:04:23,290
All right.

88
00:04:24,040 --> 00:04:26,830
So these are the strings in this array.

89
00:04:26,860 --> 00:04:29,260
Now let's call the function group anagrams.

90
00:04:29,260 --> 00:04:32,230
And let's pass this array over here to it.

91
00:04:34,410 --> 00:04:37,980
And let's run our function and let's see what we are getting.

92
00:04:39,850 --> 00:04:42,490
So you can see we have three groups over here.

93
00:04:42,520 --> 00:04:46,480
Now let's just walk through the groups and see whether this is working.

94
00:04:46,480 --> 00:04:46,720
Correct.

95
00:04:46,720 --> 00:04:47,890
So let's just grab a pen.

96
00:04:48,770 --> 00:04:49,130
All right.

97
00:04:49,130 --> 00:04:53,210
So over here we have e a t so you can see that's over here.

98
00:04:53,210 --> 00:04:56,330
Then we have t we can see that these are anagrams right.

99
00:04:56,330 --> 00:04:58,100
So we have t over here as well.

100
00:04:58,100 --> 00:05:01,190
Then we have t a n t a n is over here.

101
00:05:01,190 --> 00:05:04,370
And then we have a t a t is part of this one over here.

102
00:05:04,370 --> 00:05:08,150
So yes that's also an anagram with t and e a t eat.

103
00:05:08,150 --> 00:05:10,760
And then we have nat Nat and tan.

104
00:05:10,760 --> 00:05:11,660
These are anagrams.

105
00:05:11,660 --> 00:05:13,550
So yes they are grouped together correctly.

106
00:05:13,550 --> 00:05:17,750
And then we have bat over here and we have tab over here which are grouped correctly.

107
00:05:17,750 --> 00:05:22,670
So yes our function is working and it has identified the anagrams and group them together.

108
00:05:22,670 --> 00:05:25,670
Now let's just walk through the code and see what's happening over here.

109
00:05:25,670 --> 00:05:31,340
Now again the input over here is this, uh, string, the string, the array with strings over here.

110
00:05:31,340 --> 00:05:33,590
Now let's let's see what's happening.

111
00:05:35,570 --> 00:05:40,790
So we are calling group anagrams, and we are passing this array to the function over here.

112
00:05:40,790 --> 00:05:43,970
And once inside the function we are creating our sorted array.

113
00:05:43,970 --> 00:05:46,310
So let's write our sorted array over here.

114
00:05:47,380 --> 00:05:50,920
So this is going to take each element from the strings array.

115
00:05:50,920 --> 00:05:53,050
So we are using the dot map operator.

116
00:05:53,050 --> 00:05:57,340
So we are taking each element and we are splitting it sorting it and joining it back.

117
00:05:57,340 --> 00:05:57,640
Right.

118
00:05:57,640 --> 00:06:05,620
So this over here becomes a e t and this becomes a e t tan becomes a n t.

119
00:06:07,750 --> 00:06:10,810
And at this becomes eight again.

120
00:06:10,810 --> 00:06:18,970
And then Nat, this becomes a NT and then bat, this becomes a bt and tab also becomes a bt.

121
00:06:19,270 --> 00:06:21,250
So this is our sorted array.

122
00:06:21,250 --> 00:06:23,170
So that's at this line of code.

123
00:06:23,170 --> 00:06:25,780
And then we have our hash table over here which is empty.

124
00:06:25,810 --> 00:06:27,040
So let's just write that over here.

125
00:06:27,040 --> 00:06:30,280
So the hash table at this point is empty.

126
00:06:31,680 --> 00:06:37,920
And then we are going to have this for loop and we are iterating through the strings, which is this

127
00:06:37,920 --> 00:06:38,730
array over here.

128
00:06:38,760 --> 00:06:45,510
So I is going to take the values from zero, one, two, three, four, five and six.

129
00:06:45,510 --> 00:06:50,730
So again let's write that over here 0123, four five and six.

130
00:06:50,730 --> 00:06:57,360
Now when I is equal to zero we are checking is the value in sorted at I which is at.

131
00:06:57,390 --> 00:06:58,620
Is it there in our hash table.

132
00:06:58,620 --> 00:06:59,610
No it's not there.

133
00:06:59,610 --> 00:07:06,630
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

134
00:07:06,660 --> 00:07:07,110
e at.

135
00:07:09,510 --> 00:07:10,140
All right.

136
00:07:10,870 --> 00:07:11,950
So let's continue.

137
00:07:11,950 --> 00:07:14,230
And then we come to index one.

138
00:07:14,230 --> 00:07:18,070
So at this point we have eight over here which is already there right.

139
00:07:18,070 --> 00:07:19,660
So again we see that it's there.

140
00:07:19,660 --> 00:07:24,580
So we come over here and to this array we're going to push strings at I which is T.

141
00:07:24,580 --> 00:07:26,200
So this is added over here.

142
00:07:27,400 --> 00:07:32,380
And we go to index two and we have a and over here we see that it's not there.

143
00:07:32,380 --> 00:07:34,780
So we inserted a and T is the key.

144
00:07:34,780 --> 00:07:38,650
And the value is going to be t a n.

145
00:07:38,650 --> 00:07:38,860
Right.

146
00:07:38,860 --> 00:07:40,960
So that's an array with t a n.

147
00:07:41,790 --> 00:07:43,620
So that is what we're doing over here.

148
00:07:43,620 --> 00:07:46,050
And then we go ahead to I is equal to three.

149
00:07:46,050 --> 00:07:49,620
And we have at E and at three we have at.

150
00:07:49,620 --> 00:07:50,640
So this is already there.

151
00:07:50,640 --> 00:07:52,770
So we're going to push at E to this array.

152
00:07:52,770 --> 00:07:54,900
So we are adding a T over here.

153
00:07:54,900 --> 00:07:56,760
And then we go to the next index.

154
00:07:56,760 --> 00:07:58,020
And we have Nat.

155
00:07:58,290 --> 00:08:01,650
And over here we have a and T a and t is already there in our hash table.

156
00:08:01,650 --> 00:08:04,350
So we come to this else part over here and to this array.

157
00:08:04,350 --> 00:08:05,490
We are going to push Nat.

158
00:08:05,490 --> 00:08:07,230
So we get Nat also over here.

159
00:08:07,860 --> 00:08:10,110
And then again we go to I is equal to five.

160
00:08:10,110 --> 00:08:11,070
We have b a t.

161
00:08:11,190 --> 00:08:12,840
And over here we have abt.

162
00:08:12,870 --> 00:08:14,760
Abt is not there in our hash table.

163
00:08:14,760 --> 00:08:16,080
So we're going to insert it right.

164
00:08:16,080 --> 00:08:20,070
So abt and the value is going to be an array with b a t as the value.

165
00:08:20,730 --> 00:08:23,160
So that's happening over here at this line of code.

166
00:08:23,160 --> 00:08:25,080
And we go to I is equal to six.

167
00:08:25,080 --> 00:08:27,930
So at this point we have abt over here which is already there.

168
00:08:27,930 --> 00:08:33,270
So we come to this line of code and we are going to push to this array the value over here which is

169
00:08:33,270 --> 00:08:33,780
t a b.

170
00:08:33,780 --> 00:08:36,090
So to b is also inserted over here.

171
00:08:36,480 --> 00:08:38,040
And then we come out of the for loop.

172
00:08:38,040 --> 00:08:40,050
Because now I become seven.

173
00:08:40,050 --> 00:08:42,180
And seven is not less than seven right.

174
00:08:42,180 --> 00:08:47,040
So we come out and then we are just going to return the values of the hash table which is this part

175
00:08:47,040 --> 00:08:47,460
over here.

176
00:08:47,460 --> 00:08:50,280
So we're going to return these three arrays as an array.

177
00:08:50,280 --> 00:08:50,580
All right.

178
00:08:50,580 --> 00:08:55,920
So there's the first element in the array which has eight t and eight.

179
00:08:57,330 --> 00:08:57,690
Right.

180
00:08:57,690 --> 00:09:02,130
And similarly the second array in this array is going to have tan and nat.

181
00:09:02,130 --> 00:09:04,770
And the third array is going to have bat and tab.

182
00:09:04,770 --> 00:09:06,780
So this is how we have solved this question.

183
00:09:06,780 --> 00:09:11,430
Now let's take a quick look at the space and time complexity of this solution.

184
00:09:11,940 --> 00:09:17,700
For this let's say that n is the maximum characters in any string over here.

185
00:09:17,700 --> 00:09:19,740
So this is the maximum characters.

186
00:09:21,030 --> 00:09:25,560
So because we can have strings of different length, even though over here everything is of length three,

187
00:09:25,560 --> 00:09:27,540
we could have strings of different length.

188
00:09:27,540 --> 00:09:29,940
And let's be the number of strings.

189
00:09:29,940 --> 00:09:32,490
For example, over here we have we have seven strings.

190
00:09:32,490 --> 00:09:34,200
So s is the number of strings.

191
00:09:36,770 --> 00:09:37,190
All right.

192
00:09:37,190 --> 00:09:42,260
So over here you can see we are doing sorting on each of these strings.

193
00:09:42,260 --> 00:09:42,470
Right.

194
00:09:42,470 --> 00:09:46,550
So this is going to be n log n for each string.

195
00:09:46,550 --> 00:09:47,930
We are just taking an upper bound.

196
00:09:47,930 --> 00:09:49,550
So n is the maximum character.

197
00:09:49,550 --> 00:09:56,180
So we can just take n log n as the upper bound of the number of operations to be done, to sort a particular

198
00:09:56,180 --> 00:10:02,900
string and to sort all the strings, that is, to sort s strings, we have to do s into n log n operations.

199
00:10:02,900 --> 00:10:05,210
And then we have this for loop over here.

200
00:10:05,210 --> 00:10:11,000
In this for loop we are going to do s iterations because this is zero from zero till less than strings

201
00:10:11,000 --> 00:10:11,480
dot length.

202
00:10:11,480 --> 00:10:11,810
Right.

203
00:10:11,810 --> 00:10:13,970
So and then we have seen over here's is the number of strings.

204
00:10:13,970 --> 00:10:16,040
So over here we are doing s operations.

205
00:10:16,040 --> 00:10:17,690
And then we are just returning this right.

206
00:10:17,690 --> 00:10:18,320
So that's it.

207
00:10:18,320 --> 00:10:22,070
So again whatever we are doing inside this is just constant time operations.

208
00:10:22,070 --> 00:10:24,170
We are checking if something is there in a hash table.

209
00:10:24,170 --> 00:10:25,580
And if not we are inserting.

210
00:10:25,580 --> 00:10:27,590
So these are just constant time operations.

211
00:10:27,590 --> 00:10:31,730
So we can say that the time complexity is s into n log n plus s.

212
00:10:31,730 --> 00:10:33,920
Now s into n log n is greater than s.

213
00:10:33,920 --> 00:10:39,320
So we can say that the time complexity is just o of s into n log n.

214
00:10:40,510 --> 00:10:42,700
Now, what about the space complexity?

215
00:10:42,730 --> 00:10:44,650
Now, what are the things that take up space?

216
00:10:44,650 --> 00:10:47,050
We have this new array which we are creating.

217
00:10:47,050 --> 00:10:48,280
So that takes up space.

218
00:10:48,280 --> 00:10:50,050
And then we have this hash table.

219
00:10:50,050 --> 00:10:51,730
So that also takes up space right.

220
00:10:51,730 --> 00:10:53,530
So what about this array.

221
00:10:53,530 --> 00:10:59,380
So over here let's again take this n is the maximum characters in a particular string and s is the total

222
00:10:59,380 --> 00:11:00,700
number of strings.

223
00:11:00,700 --> 00:11:05,890
Then we can say that the sorted array is going to take up space of the order of n into s.

224
00:11:05,920 --> 00:11:07,750
Again we are just taking an upper bound, right?

225
00:11:07,750 --> 00:11:13,030
So that's why we are doing n into s, even though it may not be the case that every string has n characters,

226
00:11:13,030 --> 00:11:17,140
and the hash table is also going to have every element inside it.

227
00:11:17,140 --> 00:11:20,830
So this also is going to take up space of the order of n into s.

228
00:11:20,830 --> 00:11:26,590
So we can see that the space which is used is also of the order of n into s.

229
00:11:26,590 --> 00:11:30,130
So the space complexity is O of n into s.

230
00:11:31,080 --> 00:11:34,560
And we can also notice that there's one more thing that takes up space, right?

231
00:11:34,560 --> 00:11:35,880
We have this output array.

232
00:11:35,880 --> 00:11:38,460
This also is going to take up n into s space right.

233
00:11:38,460 --> 00:11:42,270
So again the space complexity of this solution is O of n into s.