1 00:00:00,920 --> 00:00:01,790 Hi everyone. 2 00:00:01,790 --> 00:00:05,480 So we have discussed the brute force solution for this question. 3 00:00:05,480 --> 00:00:10,400 Now let's try to see how we can solve this question in a more optimal manner. 4 00:00:10,400 --> 00:00:17,720 Now over here we have seen that for each value of I we were traversing the array again and again. 5 00:00:17,720 --> 00:00:18,110 Right. 6 00:00:18,110 --> 00:00:20,120 So we are not storing the values anywhere. 7 00:00:20,120 --> 00:00:25,010 The same value which was accessed over here is again accessed over here by traversing the array. 8 00:00:25,010 --> 00:00:25,400 Right. 9 00:00:25,400 --> 00:00:28,310 So this is not an efficient way of solving it. 10 00:00:28,310 --> 00:00:32,060 And because of that we got a time complexity of O of N square. 11 00:00:32,060 --> 00:00:32,540 Right. 12 00:00:32,540 --> 00:00:40,280 Now let's try to avoid this scenario where at each I we were traversing the array again and again. 13 00:00:40,280 --> 00:00:45,380 So for each of these N operations we were doing n operations again. 14 00:00:45,380 --> 00:00:45,620 Right. 15 00:00:45,620 --> 00:00:48,740 So that's why the time complexity was O of n square. 16 00:00:48,740 --> 00:00:52,220 And the basic reason for this was we were not storing anything. 17 00:00:52,220 --> 00:00:54,620 So let's try to store. 18 00:00:54,620 --> 00:00:59,150 So we are using some space but we will try to optimize the time complexity. 19 00:00:59,150 --> 00:00:59,630 All right. 20 00:00:59,630 --> 00:01:00,710 So let's try to do that. 21 00:01:00,710 --> 00:01:02,930 So we have a sample input. 22 00:01:02,930 --> 00:01:05,600 So let's take this as the input array. 23 00:01:05,600 --> 00:01:07,790 And the target value is equal to two. 24 00:01:08,210 --> 00:01:12,620 Now we will try to make use of a hash table to solve this. 25 00:01:12,620 --> 00:01:18,230 And the property of a hash table which we are using over here is that lookup. 26 00:01:18,230 --> 00:01:24,860 When we try to look up a value from a hash table, when we have the key is a constant time operation 27 00:01:24,860 --> 00:01:26,660 or a O of one operation. 28 00:01:26,660 --> 00:01:30,410 So this is the concept that we are going to use over here. 29 00:01:30,410 --> 00:01:34,130 And we have seen that in the previous method we were not storing anything. 30 00:01:34,130 --> 00:01:40,430 Now what we are going to do over here is as we traverse the array, we will keep storing the values 31 00:01:40,430 --> 00:01:47,330 in the hash table so that later, when we want to see whether a particular value is there in the array 32 00:01:47,330 --> 00:01:47,930 or not. 33 00:01:47,930 --> 00:01:52,580 And when that value is something that we have already traversed, we don't need to traverse the array 34 00:01:52,580 --> 00:01:56,450 again, but rather we will just access it from the hash table. 35 00:01:56,450 --> 00:01:58,730 We will just check it from the hash table. 36 00:01:58,730 --> 00:02:00,650 And we don't need to traverse the array again. 37 00:02:00,650 --> 00:02:04,370 So that's the basic thing that we are trying to implement. 38 00:02:04,370 --> 00:02:04,700 All right. 39 00:02:04,700 --> 00:02:06,530 So let's make some space over here. 40 00:02:07,040 --> 00:02:08,750 Now we will have a pointer. 41 00:02:08,750 --> 00:02:09,530 Yes definitely. 42 00:02:09,530 --> 00:02:11,270 We'll have to traverse the array once. 43 00:02:11,270 --> 00:02:16,670 So let the pointer initially point to index zero which has value two. 44 00:02:16,670 --> 00:02:18,590 And let's make a hash table. 45 00:02:18,590 --> 00:02:20,540 Initially the hash table is empty. 46 00:02:20,540 --> 00:02:20,930 All right. 47 00:02:20,960 --> 00:02:27,620 Now we will check what value we need along with two to get to the target value which is also two right. 48 00:02:27,620 --> 00:02:32,180 So this two plus something is equal to the target value which is two. 49 00:02:32,210 --> 00:02:37,100 So the needed value at this point is two minus two which is equal to zero. 50 00:02:37,100 --> 00:02:37,460 Right. 51 00:02:37,460 --> 00:02:39,590 Because two plus zero is equal to two. 52 00:02:39,590 --> 00:02:43,820 Now we will check whether this zero is there in the hash table. 53 00:02:43,820 --> 00:02:46,580 And because again we are starting the algorithm. 54 00:02:46,580 --> 00:02:48,350 So at this point it is not there. 55 00:02:48,350 --> 00:02:53,450 So if it is not there in this case zero is not there in the hash table. 56 00:02:53,450 --> 00:02:57,680 What we will do is we will insert this value into the hash table. 57 00:02:57,680 --> 00:03:00,350 So we will insert two into our hash table. 58 00:03:00,470 --> 00:03:01,580 Now let me do that. 59 00:03:01,580 --> 00:03:07,970 And again because the question says that at the end we need to return the indices of the values which 60 00:03:07,970 --> 00:03:09,080 add up to the target value. 61 00:03:09,080 --> 00:03:15,320 So when we insert two in the hash table, two is going to be the key and the value is going to be the 62 00:03:15,320 --> 00:03:15,740 index. 63 00:03:15,740 --> 00:03:20,090 So at this point we are going to insert into the hash table two zero. 64 00:03:20,120 --> 00:03:22,040 This two is this value. 65 00:03:24,180 --> 00:03:27,480 And this zero over here is this index. 66 00:03:27,480 --> 00:03:31,980 So the pair the key value pair that we're inserting over here is two zero. 67 00:03:31,980 --> 00:03:34,530 So notice what we're doing over here. 68 00:03:34,530 --> 00:03:37,410 We are storing the array into the hash table. 69 00:03:37,410 --> 00:03:37,800 Right. 70 00:03:37,800 --> 00:03:42,900 So we don't need to traverse the array again to see whether we have two or not in the array. 71 00:03:42,900 --> 00:03:46,110 So that's the basic thing that we're trying to do over here. 72 00:03:46,680 --> 00:03:47,160 All right. 73 00:03:47,190 --> 00:03:53,070 Now again we move the pointer from two to the next index which is seven. 74 00:03:53,430 --> 00:03:58,320 Now what is the needed value at this point seven plus something is equal to two. 75 00:03:58,350 --> 00:04:02,400 So the needed value is two minus seven which is equal to minus five. 76 00:04:02,400 --> 00:04:07,770 So we are going to check whether minus five is already there in the array. 77 00:04:07,770 --> 00:04:10,170 And for that we are not going to traverse the array. 78 00:04:10,170 --> 00:04:14,790 But rather we will just check whether minus five is in the hash table or not. 79 00:04:15,510 --> 00:04:15,750 Right. 80 00:04:15,750 --> 00:04:19,020 So at this point minus five is not there in the hash table. 81 00:04:19,020 --> 00:04:19,350 Right? 82 00:04:19,350 --> 00:04:21,030 It's not there in the hash table. 83 00:04:21,030 --> 00:04:22,500 So what do we do. 84 00:04:22,830 --> 00:04:25,890 We insert this seven into the hash table. 85 00:04:25,890 --> 00:04:27,150 So that's what you're going to do. 86 00:04:27,180 --> 00:04:29,670 We're inserting the array elements into the hash table. 87 00:04:29,670 --> 00:04:32,160 So let's insert seven and one. 88 00:04:32,160 --> 00:04:35,430 So this seven is the value of the array right. 89 00:04:35,430 --> 00:04:36,810 This is the key of the hash table. 90 00:04:36,810 --> 00:04:39,180 But that's the value which you have in the array. 91 00:04:39,180 --> 00:04:42,390 And over here this one is this index. 92 00:04:42,390 --> 00:04:43,020 All right. 93 00:04:43,050 --> 00:04:44,820 Now let's make some space. 94 00:04:45,270 --> 00:04:48,690 We move the pointer from 7 to 3 okay. 95 00:04:48,690 --> 00:04:51,810 So again three plus something is equal to two. 96 00:04:51,840 --> 00:04:53,400 So we need minus one. 97 00:04:53,400 --> 00:04:56,580 We are going to check whether minus one is in this array. 98 00:04:56,580 --> 00:05:00,660 Not by traversing the array but by checking whether it's there in the hash table. 99 00:05:00,660 --> 00:05:01,200 All right. 100 00:05:01,200 --> 00:05:05,850 Now you can see that minus one is not in the hash table right. 101 00:05:05,850 --> 00:05:07,500 Minus one is not in the hash table. 102 00:05:07,500 --> 00:05:08,730 So what do we do. 103 00:05:08,730 --> 00:05:11,340 We insert this three into the hash table. 104 00:05:11,340 --> 00:05:13,800 So that's 323 is this value. 105 00:05:13,800 --> 00:05:16,740 And two is the index which is this one over here. 106 00:05:16,740 --> 00:05:19,680 So we insert three and two into the hash table. 107 00:05:20,510 --> 00:05:23,630 Now we again move the pointer and we have minus one. 108 00:05:23,630 --> 00:05:26,120 So minus one plus something is equal to two. 109 00:05:26,150 --> 00:05:31,070 So the needed value in this point is two minus minus one which is equal to three. 110 00:05:31,070 --> 00:05:35,060 And we are going to check whether three is already there in the array. 111 00:05:35,060 --> 00:05:38,630 Not by traversing the array but by checking the hash table. 112 00:05:38,630 --> 00:05:44,300 And when we do that we can see yes, three is already there in the hash table, which means that three 113 00:05:44,300 --> 00:05:46,040 is there previously in the array. 114 00:05:46,040 --> 00:05:46,430 Right. 115 00:05:46,430 --> 00:05:48,500 So yes we have found our solution. 116 00:05:48,500 --> 00:05:48,950 Right. 117 00:05:48,950 --> 00:05:50,990 This means three is there in the array. 118 00:05:50,990 --> 00:05:52,400 So we have the answer. 119 00:05:52,400 --> 00:05:54,950 And remember we need to return the indices. 120 00:05:54,950 --> 00:05:59,960 So the index of value three in the array is this two over here. 121 00:05:59,960 --> 00:06:06,290 So we are going to return this two and this index over here already we have the pointer which is pointing 122 00:06:06,320 --> 00:06:07,130 to index three. 123 00:06:07,130 --> 00:06:07,460 Right. 124 00:06:07,460 --> 00:06:11,270 So we are going to return these two indices this two and this three. 125 00:06:11,270 --> 00:06:14,060 That's two comma three which is our answer. 126 00:06:14,600 --> 00:06:18,140 Now again quickly let's revise what we did. 127 00:06:18,530 --> 00:06:22,550 Basically we are ensuring that we need to traverse the array only once. 128 00:06:22,550 --> 00:06:30,140 And if when we whenever we encounter an element of the array, we check whether the needed value is 129 00:06:30,140 --> 00:06:32,570 already there in the array because it's a pair, right? 130 00:06:32,570 --> 00:06:33,560 We need two values. 131 00:06:33,560 --> 00:06:40,400 For example two we needed zero for seven, we needed five for three, we needed minus one, etc. so 132 00:06:40,400 --> 00:06:46,100 when we were at the index which had the value two, we are checking whether zero is already there in 133 00:06:46,100 --> 00:06:50,060 the array, not by traversing the array, but by checking the hash table. 134 00:06:50,060 --> 00:06:55,850 Similarly, when we were at the index which had the value seven, this one over here, we were checking 135 00:06:55,850 --> 00:07:00,770 whether five is already there in the array by checking whether it's there in the hash table, and if 136 00:07:00,770 --> 00:07:02,240 it's not, we were inserting right. 137 00:07:02,240 --> 00:07:04,400 So at this point we inserted two zero. 138 00:07:04,400 --> 00:07:06,020 Then we inserted seven one. 139 00:07:06,020 --> 00:07:08,030 At this point we inserted three two. 140 00:07:08,510 --> 00:07:13,910 And when we reached over here we checked whether we have three in the array in the previous elements 141 00:07:13,910 --> 00:07:18,590 of the array which were already traversed not by again traversing the array, but by checking the hash 142 00:07:18,590 --> 00:07:19,040 table. 143 00:07:19,040 --> 00:07:20,840 And we saw it's there right. 144 00:07:20,840 --> 00:07:22,070 So we got the answer. 145 00:07:22,070 --> 00:07:25,220 And the answer is minus one and three. 146 00:07:25,220 --> 00:07:26,330 These add up to two. 147 00:07:26,330 --> 00:07:31,370 And we return the indices because we are storing the index over here we got the index of three from 148 00:07:31,370 --> 00:07:33,620 the hash table and the index of minus one. 149 00:07:33,620 --> 00:07:36,890 We got it because that's that was stored in the pointer right. 150 00:07:36,890 --> 00:07:39,470 So we returned two comma three which is the answer. 151 00:07:39,470 --> 00:07:43,820 Now let's look at the space and time complexity of this solution. 152 00:07:43,820 --> 00:07:44,240 Right. 153 00:07:44,240 --> 00:07:48,290 So the time complexity of this solution is O of n. 154 00:07:48,290 --> 00:07:53,870 We have seen that the time complexity of the brute force solution where we had two for loops. 155 00:07:53,870 --> 00:07:54,080 Right. 156 00:07:54,080 --> 00:07:55,430 So there was a nested for loop. 157 00:07:55,430 --> 00:07:58,190 The time complexity was O of n square. 158 00:07:58,190 --> 00:08:01,700 So we were able to improve upon that to O of n. 159 00:08:01,700 --> 00:08:02,360 Why is that. 160 00:08:02,360 --> 00:08:05,060 So we are traversing the array only once, right? 161 00:08:05,060 --> 00:08:09,830 We are traversing it only once, which is what we have done, which is what we are doing over here. 162 00:08:10,700 --> 00:08:16,730 And remember accessing from the hash table when we know the key is a constant time operation. 163 00:08:16,730 --> 00:08:21,440 So checking whether it's in it's a particular value is in the hash table. 164 00:08:21,440 --> 00:08:25,070 And if it's there taking the index is a constant time operation. 165 00:08:25,070 --> 00:08:27,860 So that's not adding to our time complexity. 166 00:08:27,860 --> 00:08:30,650 So the time complexity over here is O of N. 167 00:08:30,650 --> 00:08:34,430 And the space complexity over here is also O of n. 168 00:08:34,430 --> 00:08:34,850 Right. 169 00:08:34,850 --> 00:08:39,260 Because max we need to insert n pairs into the hash table. 170 00:08:39,260 --> 00:08:39,800 Right. 171 00:08:39,800 --> 00:08:42,050 Let's say we have these five elements. 172 00:08:42,050 --> 00:08:53,270 So in the worst case our hash table will have five pairs right 207132 minus one and three and four comma 173 00:08:53,270 --> 00:08:53,900 four. 174 00:08:53,900 --> 00:08:54,080 Right. 175 00:08:54,080 --> 00:08:55,670 So that's the worst case scenario. 176 00:08:55,670 --> 00:08:56,870 And this is n elements. 177 00:08:56,870 --> 00:09:01,970 So if there are n elements in the input array the hash table will have at the most n pairs. 178 00:09:01,970 --> 00:09:06,590 So that's why because we are storing this extra hash table. 179 00:09:06,590 --> 00:09:10,430 That's why the space complexity of the solution is O of n. 180 00:09:10,430 --> 00:09:14,330 So in the brute force solution the space complexity was O of one. 181 00:09:14,330 --> 00:09:21,530 But by increasing the space used to O of N, we were able to improve the time complexity in the brute 182 00:09:21,530 --> 00:09:22,010 force solution. 183 00:09:22,010 --> 00:09:26,150 It was O of n square, but we were able to improve it to O of n.