1 00:00:00,510 --> 00:00:01,530 Welcome back. 2 00:00:01,530 --> 00:00:04,500 Now let's try to see how we can solve this question. 3 00:00:04,500 --> 00:00:08,100 Now over here I have two anagrams car and Ark. 4 00:00:08,130 --> 00:00:08,460 Ark. 5 00:00:08,460 --> 00:00:08,820 Right. 6 00:00:08,820 --> 00:00:14,310 You can see that the same letters are used for both these words and exactly the same number of times. 7 00:00:14,310 --> 00:00:15,930 So these two are anagrams. 8 00:00:15,930 --> 00:00:19,860 Now, if we just sort these letters, let's just sort these letters. 9 00:00:19,860 --> 00:00:23,430 So if we sort the letters in car we will get a car. 10 00:00:23,430 --> 00:00:25,500 Now let's sort the letters in Ark. 11 00:00:25,500 --> 00:00:28,560 So if we do that again you can see we will get a car. 12 00:00:28,560 --> 00:00:35,340 So if we have two anagrams and if we just sort them, you can see that we will get the same word right. 13 00:00:35,340 --> 00:00:40,830 So we will try to make use of this property, this interesting observation to try to solve this question. 14 00:00:40,830 --> 00:00:43,620 So let's say this is the array which is given to us. 15 00:00:43,620 --> 00:00:45,570 And you can see that it has various strings in it. 16 00:00:45,570 --> 00:00:47,880 Now let's write the indices of this array. 17 00:00:47,880 --> 00:00:51,060 So we have 012345 and six. 18 00:00:51,060 --> 00:00:52,380 So these are the indices. 19 00:00:52,380 --> 00:00:54,720 Now let's create another array. 20 00:00:54,720 --> 00:01:00,360 And in the the new array which you are creating over here is going to consist of these strings in the 21 00:01:00,360 --> 00:01:01,170 sorted manner. 22 00:01:01,170 --> 00:01:05,430 So we are going to take each string sorted and then put it into our new array. 23 00:01:05,430 --> 00:01:07,260 So over here we have Ark. 24 00:01:07,290 --> 00:01:09,660 Now when we sort this we will get a car. 25 00:01:09,660 --> 00:01:11,370 So that's going to be at index zero. 26 00:01:11,370 --> 00:01:13,140 And over here we have a b c. 27 00:01:13,140 --> 00:01:18,000 When we sort this we will again get a b c and then c a r becomes a c r. 28 00:01:18,000 --> 00:01:26,040 And we continue c a t will become act and act will remain as it is act itself and then a, c, b will 29 00:01:26,040 --> 00:01:30,270 become a, B, C and ATC will become act. 30 00:01:30,270 --> 00:01:36,810 So we have formed a new array, and each string in the original array is sorted and put into the new 31 00:01:36,810 --> 00:01:37,020 array. 32 00:01:37,020 --> 00:01:38,190 So this is our new array. 33 00:01:38,220 --> 00:01:41,190 Now we can just use the property right. 34 00:01:41,190 --> 00:01:45,210 We know that two anagrams, if they are sorted they will have they will look the same right. 35 00:01:45,210 --> 00:01:48,510 For example we have a r c and we have c r. 36 00:01:48,510 --> 00:01:50,040 So we have seen that example right. 37 00:01:50,040 --> 00:01:55,560 So after sorting these we can see that over here in the sorted array these two are just the same. 38 00:01:55,560 --> 00:01:58,050 So now we can just use a hash table. 39 00:01:58,050 --> 00:02:00,000 And we will just iterate. 40 00:02:00,000 --> 00:02:04,770 Or we will just go through the array which is given to us by having an index. 41 00:02:04,770 --> 00:02:04,980 Right. 42 00:02:04,980 --> 00:02:07,770 So we'll have I pointing to zero then one etc.. 43 00:02:07,770 --> 00:02:11,190 So we will iterate through the arrays, these two arrays together. 44 00:02:11,190 --> 00:02:16,470 And then we will check if whatever is there in the sorted array is there in our hash table. 45 00:02:16,470 --> 00:02:23,190 If it is not there, then we will use the value in the sorted array as the key, and we will use the 46 00:02:23,190 --> 00:02:27,930 same, uh, the the value in the same index in the original array as the value. 47 00:02:27,930 --> 00:02:30,090 And we will push it to our hash table. 48 00:02:30,090 --> 00:02:35,370 And if we do that, we will be able to group all the anagrams together, because we know that the anagrams 49 00:02:35,370 --> 00:02:37,740 will look the same when they are sorted. 50 00:02:37,740 --> 00:02:38,760 So let's proceed. 51 00:02:38,760 --> 00:02:40,980 So initially I is equal to zero. 52 00:02:40,980 --> 00:02:42,150 So we are at index zero. 53 00:02:42,150 --> 00:02:43,800 And over here we have ACR. 54 00:02:43,800 --> 00:02:45,660 ACR is not there in our hash table. 55 00:02:45,660 --> 00:02:47,130 So let's make an entry. 56 00:02:47,130 --> 00:02:48,900 So the key is going to be ACR. 57 00:02:48,900 --> 00:02:53,040 And the value is going to be an array with the value RC which is over here. 58 00:02:53,040 --> 00:02:54,450 So let's do that over here. 59 00:02:55,550 --> 00:02:55,970 All right. 60 00:02:55,970 --> 00:02:57,800 Now we move to index one. 61 00:02:57,800 --> 00:03:01,280 So at index one in the sorted array we have ABC. 62 00:03:01,280 --> 00:03:04,490 And we see that ABC is not there in our hash table. 63 00:03:04,490 --> 00:03:09,110 So we are going to insert the key value pair where the key is going to be ABC. 64 00:03:09,110 --> 00:03:13,490 And the value is what we have in the original array which is ABC itself. 65 00:03:13,490 --> 00:03:15,050 So let's go ahead and insert that. 66 00:03:15,050 --> 00:03:16,310 And this is going to be an array. 67 00:03:16,310 --> 00:03:18,320 So the value is going to be an array. 68 00:03:18,440 --> 00:03:20,450 Now we proceed to index two. 69 00:03:20,450 --> 00:03:22,790 At index two we have ACR over here. 70 00:03:22,790 --> 00:03:26,060 And we see that ACR is already there in our hash table. 71 00:03:26,060 --> 00:03:33,830 So we are going to push the value in the original array at index two which is car or car into this value 72 00:03:33,830 --> 00:03:34,490 array over here. 73 00:03:34,490 --> 00:03:35,420 So let's do that. 74 00:03:35,420 --> 00:03:37,160 So we get car over here. 75 00:03:37,160 --> 00:03:38,930 Now we move to index three. 76 00:03:38,930 --> 00:03:40,160 So we have act. 77 00:03:40,190 --> 00:03:41,990 Act is not there in our hash table. 78 00:03:41,990 --> 00:03:43,910 So let's insert this as the key. 79 00:03:43,910 --> 00:03:45,710 And the value is going to be cat. 80 00:03:45,710 --> 00:03:47,270 So let's insert that over here. 81 00:03:48,110 --> 00:03:48,560 All right. 82 00:03:48,560 --> 00:03:50,240 And then we move to index four. 83 00:03:50,240 --> 00:03:53,630 So at index four we have act and act. 84 00:03:53,630 --> 00:03:55,370 So act is already there. 85 00:03:55,370 --> 00:03:56,870 So we have the key. 86 00:03:56,870 --> 00:04:01,190 So we're going to push this value into the the values array over here. 87 00:04:01,190 --> 00:04:02,000 So let's do that. 88 00:04:02,000 --> 00:04:03,500 So we get act over here. 89 00:04:04,480 --> 00:04:06,250 Now we proceed to index five. 90 00:04:06,250 --> 00:04:11,170 We have ABC as the key, and we see that ABC is already there in the hash table as a key. 91 00:04:11,170 --> 00:04:15,220 So we're going to push the value ACB into this array over here. 92 00:04:15,220 --> 00:04:15,970 So let's do that. 93 00:04:15,970 --> 00:04:19,600 So we get ACB over here and then we move to I is equal to six. 94 00:04:19,600 --> 00:04:23,830 So at this point the sorted array has the value act. 95 00:04:23,860 --> 00:04:25,780 Act is already there in our hash table. 96 00:04:25,780 --> 00:04:30,670 So we are going to push this value which is which is ATC into this array over here. 97 00:04:30,670 --> 00:04:31,330 So let's do that. 98 00:04:31,330 --> 00:04:32,950 So we get ATC over here. 99 00:04:33,490 --> 00:04:33,820 All right. 100 00:04:33,820 --> 00:04:34,750 So that's that's it. 101 00:04:34,750 --> 00:04:36,790 So we have formed our hash table. 102 00:04:36,790 --> 00:04:40,120 Now we just need to return these values right. 103 00:04:40,120 --> 00:04:42,640 So we just need to return these values in an array. 104 00:04:42,640 --> 00:04:44,470 So that's going to be the answer. 105 00:04:44,470 --> 00:04:47,860 So you can see we have r c and c r as an array. 106 00:04:47,890 --> 00:04:49,690 Then we have ABC and ACB. 107 00:04:49,690 --> 00:04:50,890 So that's this array over here. 108 00:04:50,890 --> 00:04:54,850 Then we have Cat Act and ATC as an array which is this array over here. 109 00:04:54,850 --> 00:04:56,080 And that is our solution. 110 00:04:56,080 --> 00:04:59,830 So we have grouped the anagrams together and then returned it as an array. 111 00:04:59,830 --> 00:05:03,820 Now let's take a quick look at the time and space complexity of this solution. 112 00:05:03,820 --> 00:05:10,480 Now for the time complexity to to analyze the time complexity, let's say that's is the number of strings 113 00:05:10,480 --> 00:05:13,480 in the array which is given to us, which is this array over here. 114 00:05:13,480 --> 00:05:17,500 And let's say that n is the maximum number of characters in a string. 115 00:05:17,500 --> 00:05:17,890 All right. 116 00:05:17,890 --> 00:05:23,140 So we are just taking the maximum number of characters because as you know, big O analysis just tries 117 00:05:23,140 --> 00:05:25,930 to find out the upper bound of the time complexity. 118 00:05:25,960 --> 00:05:32,890 Now to sort one of the strings, we will take n log n time, write n log n time complexity or operations. 119 00:05:32,890 --> 00:05:39,580 Therefore, to sort s strings we are going to take s into n log n operations, or the time complexity 120 00:05:39,580 --> 00:05:43,120 is going to be of the order of s into n log n. 121 00:05:43,120 --> 00:05:48,250 Again, n log n is to sort each string right because n is the maximum number of characters. 122 00:05:48,250 --> 00:05:49,750 So this is going to be the upper bound. 123 00:05:49,750 --> 00:05:51,250 And then we have s strings. 124 00:05:51,250 --> 00:05:53,080 So that's why we are multiplying this with s. 125 00:05:53,080 --> 00:05:56,380 So the time complexity is o of s into n log n. 126 00:05:56,380 --> 00:05:58,420 Now what about the space complexity. 127 00:05:58,420 --> 00:06:00,250 Let's think of what all takes space. 128 00:06:00,250 --> 00:06:05,830 And before that also after we go, after we loop through the um the array. 129 00:06:05,830 --> 00:06:06,070 Right. 130 00:06:06,070 --> 00:06:09,370 These two arrays, we are doing that after we are sorting them, we are looping through them. 131 00:06:09,370 --> 00:06:09,670 Right. 132 00:06:09,670 --> 00:06:12,550 So at that point we are just doing constant operations. 133 00:06:12,550 --> 00:06:17,080 Again, we know that for looping through them, we are doing s operations because there are s strings, 134 00:06:17,080 --> 00:06:19,630 but then s is less than s into n log n. 135 00:06:19,630 --> 00:06:21,010 So we can just neglect this. 136 00:06:21,010 --> 00:06:26,140 And then when we are looping through them we are doing just constant time operations like checking if 137 00:06:26,140 --> 00:06:28,780 the value is there in a hash table and if not pushing. 138 00:06:28,780 --> 00:06:30,940 So these are just constant time operations. 139 00:06:30,940 --> 00:06:31,360 All right. 140 00:06:31,360 --> 00:06:33,580 Now let's proceed to the space complexity. 141 00:06:33,580 --> 00:06:36,520 Now what all takes up space that can scale right. 142 00:06:36,520 --> 00:06:38,230 We are creating a sorted array over here. 143 00:06:38,230 --> 00:06:39,760 So we can see that over here. 144 00:06:39,760 --> 00:06:41,650 Then we have a hash table. 145 00:06:41,650 --> 00:06:42,760 So that takes up space. 146 00:06:42,760 --> 00:06:44,710 And then we have our output array. 147 00:06:44,710 --> 00:06:47,410 So these are the three things that take up space over here. 148 00:06:47,410 --> 00:06:51,790 Now the sorted array is going to take up space of the order of s into n. 149 00:06:51,790 --> 00:06:56,770 Because again n is the maximum characters and s is the number of strings which is there in the array 150 00:06:56,770 --> 00:06:57,670 which is given to us. 151 00:06:57,670 --> 00:07:03,280 So this is the upper bound right s into n for the space that the sorted array can take up, right. 152 00:07:03,280 --> 00:07:05,470 So that's again a constant into s into n. 153 00:07:05,470 --> 00:07:07,630 And we are just neglecting the constant. 154 00:07:07,630 --> 00:07:11,860 And the output array is also going to take up space of the order of s into n. 155 00:07:11,860 --> 00:07:14,680 And the hash table also is going to have everything inside it. 156 00:07:14,680 --> 00:07:14,950 Right. 157 00:07:14,950 --> 00:07:17,950 So each of these elements is going to be there in the hash table. 158 00:07:17,950 --> 00:07:21,340 And then we are have some more space taken up for the keys. 159 00:07:21,340 --> 00:07:25,810 But again the space taken up is going to be of the order of s into n. 160 00:07:25,810 --> 00:07:31,270 So that's why we can say that the space complexity of this solution is O of s into n.