1 00:00:00,860 --> 00:00:01,730 Hi everyone. 2 00:00:01,730 --> 00:00:04,040 So we have coded the optimal solution. 3 00:00:04,040 --> 00:00:07,760 Now let's take a test case and walk through the code that we've written. 4 00:00:07,760 --> 00:00:08,450 For this. 5 00:00:08,450 --> 00:00:14,270 Let's take the RA two minus one five three and let the target value be equal to four. 6 00:00:14,600 --> 00:00:18,110 Now let's write the indices of the given array. 7 00:00:18,110 --> 00:00:20,720 So this is 012 and three. 8 00:00:20,720 --> 00:00:21,380 All right. 9 00:00:21,380 --> 00:00:24,380 Now we are let's say we have called this function. 10 00:00:24,380 --> 00:00:27,410 And we have passed the array two minus one five three. 11 00:00:27,410 --> 00:00:29,750 And we have passed the target value four. 12 00:00:29,750 --> 00:00:32,930 So at this point we will initialize the hash table. 13 00:00:32,930 --> 00:00:35,630 And it's going to be empty at this point. 14 00:00:35,630 --> 00:00:36,230 All right. 15 00:00:36,260 --> 00:00:40,160 Now we have now declared a variable needed value. 16 00:00:40,160 --> 00:00:42,080 And then we enter the for loop. 17 00:00:42,080 --> 00:00:46,340 Now we can see that in this optimal solution we have only one for loop. 18 00:00:46,340 --> 00:00:52,130 So that's the reason why we have been able to optimize the time complexity compared to the brute force 19 00:00:52,130 --> 00:00:52,730 solution. 20 00:00:52,730 --> 00:00:55,760 Now initially the value of I is equal to zero. 21 00:00:56,030 --> 00:01:04,880 So at this point we come inside the for loop and at the i'th index the needed value is calculated right. 22 00:01:04,880 --> 00:01:06,290 So at the ith index. 23 00:01:06,290 --> 00:01:09,770 In this case at the zeroth index the value is two. 24 00:01:09,800 --> 00:01:15,260 It's the value that we have so needed value is equal to target value minus array at I array at I is 25 00:01:15,260 --> 00:01:15,920 equal to two. 26 00:01:15,950 --> 00:01:18,530 So needed value is equal to four minus two. 27 00:01:18,530 --> 00:01:18,800 Right. 28 00:01:18,800 --> 00:01:20,300 So needed value is equal to two. 29 00:01:20,330 --> 00:01:21,770 Now what do we mean with this. 30 00:01:21,770 --> 00:01:27,140 If we have two and if we have another two then we can get to the target value which is four. 31 00:01:27,140 --> 00:01:31,550 So the needed value for two and this one to work is equal to two. 32 00:01:31,580 --> 00:01:33,410 So we have calculated the needle value. 33 00:01:33,410 --> 00:01:37,280 And we are going to check whether the needed value is in the hash table. 34 00:01:37,280 --> 00:01:41,060 Now at this point our hash table is empty so it's not there. 35 00:01:41,060 --> 00:01:47,660 So because it's not there we come to the else part and we insert the value into the hash table. 36 00:01:47,660 --> 00:01:48,980 And what are we inserting. 37 00:01:48,980 --> 00:01:52,790 We are inserting a key value pair in the hash table. 38 00:01:52,790 --> 00:01:54,860 Now the key is array of I. 39 00:01:57,170 --> 00:01:58,880 And the value is the index. 40 00:01:58,880 --> 00:02:00,500 So that's what we're doing over here right. 41 00:02:00,500 --> 00:02:03,860 So at the key array of I which is equal to two. 42 00:02:03,860 --> 00:02:07,160 At this point we are inserting the index which is equal to zero. 43 00:02:07,160 --> 00:02:09,890 So we are inserting the pair two zero. 44 00:02:10,130 --> 00:02:13,910 Now again we increment I by one. 45 00:02:13,910 --> 00:02:15,890 So I is equal to one at this point. 46 00:02:15,890 --> 00:02:18,800 And the needed value is equal to five. 47 00:02:18,800 --> 00:02:19,010 Right. 48 00:02:19,010 --> 00:02:23,810 Because at this at the index one the value which we have is minus one. 49 00:02:23,810 --> 00:02:28,130 So minus one plus something is equal to four which is the target value. 50 00:02:28,130 --> 00:02:33,320 So the needed value this is the needed value is equal to four minus minus one which is equal to five 51 00:02:33,320 --> 00:02:33,650 right. 52 00:02:33,860 --> 00:02:35,810 The needed value at this point is five. 53 00:02:35,810 --> 00:02:39,890 Again we are going to check whether the needed value is in our hash table. 54 00:02:39,890 --> 00:02:40,880 It's not there. 55 00:02:40,880 --> 00:02:45,530 So we insert array of I and the index into our hash table. 56 00:02:45,530 --> 00:02:46,520 So let's do that. 57 00:02:46,520 --> 00:02:51,710 So array of I at this point is minus one and the index is equal to one. 58 00:02:51,710 --> 00:02:58,280 So again you can notice that we are actually inserting the values of the given array into the hash table. 59 00:02:58,280 --> 00:03:03,470 So that we don't need to traverse the array again to access and to check whether the particular value 60 00:03:03,470 --> 00:03:04,880 is there or not in the array. 61 00:03:04,880 --> 00:03:05,960 So that's the aim. 62 00:03:05,960 --> 00:03:08,510 Now again we are incrementing I by one. 63 00:03:08,510 --> 00:03:10,880 And it's still less than array dot length. 64 00:03:10,880 --> 00:03:15,080 Array dot length at this point is equal to four of this array of the given array is four. 65 00:03:15,080 --> 00:03:16,730 So I is equal to two. 66 00:03:16,760 --> 00:03:18,020 Two is less than four. 67 00:03:18,020 --> 00:03:19,970 So we come again inside. 68 00:03:19,970 --> 00:03:24,560 And at this point at the second index the value is five. 69 00:03:24,560 --> 00:03:27,620 Now five plus needed value is equal to four. 70 00:03:27,620 --> 00:03:30,800 So needed value is four minus five which is minus one. 71 00:03:30,800 --> 00:03:32,090 So this is the needed value. 72 00:03:32,090 --> 00:03:35,450 And we check whether the needed value is in the hash table. 73 00:03:35,450 --> 00:03:39,260 And we can see that yes we have the needed value in the hash table. 74 00:03:39,260 --> 00:03:40,910 So we have found the answer. 75 00:03:41,360 --> 00:03:50,570 So this means that if the value in the array at the second index is part of a pair which adds to the 76 00:03:50,570 --> 00:03:55,280 target value, then the other value which is required also has to be there in the hash table. 77 00:03:55,280 --> 00:03:55,430 Right. 78 00:03:55,430 --> 00:03:56,600 So that's what we are checking. 79 00:03:56,600 --> 00:03:58,250 And we found that it is there. 80 00:03:58,250 --> 00:04:01,190 So five will be true if we have minus one. 81 00:04:01,190 --> 00:04:02,750 And we just found that it is there. 82 00:04:02,750 --> 00:04:05,600 So five comma minus one add up to four. 83 00:04:05,600 --> 00:04:08,210 And because we have to return the indices. 84 00:04:08,210 --> 00:04:10,970 So let's take the indices that's two and one. 85 00:04:10,970 --> 00:04:12,440 And we return the indices. 86 00:04:12,440 --> 00:04:14,150 And we have our answer. 87 00:04:14,180 --> 00:04:16,100 Now let me make some space over here. 88 00:04:17,480 --> 00:04:21,260 Now the time complexity of this solution is equal to O of n. 89 00:04:21,260 --> 00:04:22,460 Now why is that so? 90 00:04:22,460 --> 00:04:25,550 Because we have to traverse the array only once. 91 00:04:25,550 --> 00:04:27,650 And we're doing that in this for loop. 92 00:04:27,650 --> 00:04:27,920 Right. 93 00:04:27,920 --> 00:04:29,900 So we are traversing the array only once. 94 00:04:29,900 --> 00:04:33,500 And remember we are accessing values from the hash table. 95 00:04:33,500 --> 00:04:36,410 Now accessing a value from the hash table. 96 00:04:36,410 --> 00:04:41,060 When you know the uh, key that's a constant time operation. 97 00:04:41,060 --> 00:04:41,390 Right. 98 00:04:41,390 --> 00:04:45,170 So that does not add up to our time complexity. 99 00:04:45,170 --> 00:04:51,680 Therefore the time complexity of this algorithm is O of N, and the space complexity is also O of n. 100 00:04:51,680 --> 00:04:58,010 Because we are making this hash table, and this hash table in the worst case will have n key value 101 00:04:58,010 --> 00:04:58,580 pairs, right. 102 00:04:58,580 --> 00:05:01,940 If let's say for each of these we had to insert it. 103 00:05:01,940 --> 00:05:05,360 Then also this hash table will have only n key value pairs. 104 00:05:05,360 --> 00:05:08,630 So the space complexity of this algorithm is O of n.