1
00:00:00,900 --> 00:00:03,270
Hi everyone, I hope you have given it a shot.

2
00:00:03,300 --> 00:00:07,830
Now let's code together the solution that we discussed in the previous video.

3
00:00:07,830 --> 00:00:15,330
Now for this, let's start by creating a function and let's call this function find indices some given.

4
00:00:16,590 --> 00:00:22,380
And as mentioned in the question, we pass the array and the target value into this function.

5
00:00:23,500 --> 00:00:26,680
Now we are going to initialize a hash table.

6
00:00:26,680 --> 00:00:33,370
That's how we are going to avoid the need for two for loops, which was costing us a lot of complexity

7
00:00:33,370 --> 00:00:35,680
which was increasing increasing the time complexity.

8
00:00:35,680 --> 00:00:38,290
So let's call this hash table itself.

9
00:00:38,820 --> 00:00:42,150
And initially this hash table is empty.

10
00:00:44,680 --> 00:00:48,130
Now we need to traverse the array once.

11
00:00:48,130 --> 00:00:49,870
For this we will use a for loop.

12
00:00:49,870 --> 00:00:53,980
But before that let me just create a variable needed value.

13
00:00:54,010 --> 00:00:58,630
We will use this to check whether the needed value is already there in the hash table.

14
00:00:58,780 --> 00:01:02,260
Now for traversing the array once we are using the for loop.

15
00:01:02,260 --> 00:01:04,030
So let's write for.

16
00:01:04,030 --> 00:01:08,380
Let I is equal to zero I less than.

17
00:01:09,170 --> 00:01:10,370
Array dot length.

18
00:01:12,160 --> 00:01:14,770
Because we need to go through the complete array.

19
00:01:14,770 --> 00:01:15,280
Right.

20
00:01:15,280 --> 00:01:20,950
So we are doing it up to I less than array dot length and I plus plus.

21
00:01:23,520 --> 00:01:26,160
Now inside the for loop.

22
00:01:26,160 --> 00:01:28,890
First let's calculate the needed value.

23
00:01:28,890 --> 00:01:29,850
Now again over here.

24
00:01:29,850 --> 00:01:32,160
Let me just show what's happening.

25
00:01:32,160 --> 00:01:33,420
Let's take an example.

26
00:01:33,420 --> 00:01:36,510
Let's say the given array is again 123.

27
00:01:37,050 --> 00:01:40,290
And let's say the target value is three.

28
00:01:40,860 --> 00:01:42,300
Or let's take another example.

29
00:01:42,300 --> 00:01:44,220
Let's say 1234.

30
00:01:44,220 --> 00:01:47,460
And let's say the target value is um seven.

31
00:01:47,940 --> 00:01:48,870
So let me write that.

32
00:01:48,870 --> 00:01:50,610
So target value is equal to seven.

33
00:01:51,300 --> 00:01:53,370
To make the logic clear.

34
00:01:53,370 --> 00:01:57,060
Now we are inside the for loop and I is equal to zero at this point.

35
00:01:57,060 --> 00:02:01,680
Now in the zeroth index the value in the given array is equal to one.

36
00:02:01,680 --> 00:02:04,920
Now we are going to calculate the needed value at this point.

37
00:02:04,920 --> 00:02:10,020
So the needed value is nothing but the target value minus the value that we have.

38
00:02:10,020 --> 00:02:10,470
Right.

39
00:02:10,470 --> 00:02:12,540
So needed value is equal to.

40
00:02:13,240 --> 00:02:14,380
Target value.

41
00:02:16,480 --> 00:02:19,060
Minus array at I.

42
00:02:20,440 --> 00:02:20,950
Okay.

43
00:02:20,950 --> 00:02:25,540
So in this case we have an array at I is one and the needed value.

44
00:02:25,540 --> 00:02:31,180
Let me write that as n v needed value is equal to seven minus one which is equal to six.

45
00:02:31,330 --> 00:02:35,290
Now we are going to check whether this six already occurred before.

46
00:02:35,290 --> 00:02:37,090
Now we are starting with this iteration.

47
00:02:37,090 --> 00:02:40,630
So yes it does not make sense because it's going to be empty anyway.

48
00:02:40,630 --> 00:02:41,590
The hash table is empty.

49
00:02:41,590 --> 00:02:46,090
But going forward this is what we will be repeatedly doing in each iteration.

50
00:02:46,090 --> 00:02:47,500
So let's do that over here.

51
00:02:47,500 --> 00:02:51,310
We're going to check whether the needed value is in the hash table.

52
00:02:51,310 --> 00:02:55,930
So if needed value in hash table.

53
00:02:55,930 --> 00:03:01,000
So if it is there it means that it already occurred in the array before.

54
00:03:01,000 --> 00:03:01,270
Right.

55
00:03:01,270 --> 00:03:02,650
So we have found the answer.

56
00:03:02,650 --> 00:03:05,230
Now if it is there we are going to return.

57
00:03:06,110 --> 00:03:08,000
The indices, the required indices.

58
00:03:08,000 --> 00:03:16,130
Now in this case the one index is I because we are at the I th value right and the other index will

59
00:03:16,130 --> 00:03:21,380
be stored as the value when we pass the needed value as a key in the hash table.

60
00:03:21,380 --> 00:03:21,710
All right.

61
00:03:21,710 --> 00:03:26,660
So let's just hold this for a minute and let's write the else part and come back so that it will be

62
00:03:26,660 --> 00:03:30,290
clear because we have not yet written what comes into the hash table.

63
00:03:30,290 --> 00:03:30,590
Right.

64
00:03:30,590 --> 00:03:33,740
So let me just leave that for a moment and write the else part.

65
00:03:33,740 --> 00:03:38,000
So if the needed value is not there in the hash table, what do we do?

66
00:03:38,030 --> 00:03:39,530
We insert the value.

67
00:03:39,560 --> 00:03:42,230
We insert a of I into the hash table.

68
00:03:42,230 --> 00:03:44,360
So let's write that hash table.

69
00:03:45,660 --> 00:03:47,160
At a of I.

70
00:03:47,190 --> 00:03:49,170
So the key is array of I.

71
00:03:49,170 --> 00:03:50,730
The key is the array of the value.

72
00:03:50,730 --> 00:03:52,740
In this case the key is one.

73
00:03:52,740 --> 00:03:53,970
So 1234.

74
00:03:54,000 --> 00:03:56,520
These are going to be the keys in the hash table.

75
00:03:56,610 --> 00:03:59,250
And the value will be the index.

76
00:03:59,250 --> 00:04:01,470
Because we need to return the index at the end of the day.

77
00:04:01,470 --> 00:04:01,770
Right.

78
00:04:01,770 --> 00:04:04,980
So we need to be able to read the index from the hash table.

79
00:04:04,980 --> 00:04:07,530
That's why we are storing the value as the index.

80
00:04:07,530 --> 00:04:10,170
And the key is the value of the array.

81
00:04:10,170 --> 00:04:13,560
So in this case we are going to store in the hash table.

82
00:04:13,560 --> 00:04:15,030
Let me write that also over here.

83
00:04:15,030 --> 00:04:19,890
So in the first iteration when RA of I is equal to one we are in the hash table.

84
00:04:19,890 --> 00:04:21,420
Initially the hash table is empty.

85
00:04:21,450 --> 00:04:27,120
Now at this point we are going to see that the required value needed value, which is six, is not there

86
00:04:27,120 --> 00:04:27,900
in the hash table.

87
00:04:27,900 --> 00:04:30,840
So let's store one in the hash table.

88
00:04:30,840 --> 00:04:33,570
And we also need to store the index of one.

89
00:04:33,570 --> 00:04:35,760
So we are going to store one and zero.

90
00:04:35,760 --> 00:04:36,930
So one is the value.

91
00:04:36,930 --> 00:04:38,010
This one over here.

92
00:04:38,760 --> 00:04:40,560
And zero is the index.

93
00:04:40,560 --> 00:04:42,210
This is at the zeroth index.

94
00:04:42,210 --> 00:04:42,720
All right.

95
00:04:42,720 --> 00:04:46,170
So we're going to keep doing this now in the next iteration.

96
00:04:46,170 --> 00:04:48,600
So over here you can see if needed value.

97
00:04:48,600 --> 00:04:51,360
So let's just complete this part which we left for a moment.

98
00:04:51,360 --> 00:04:58,230
So when the needed value is in the hash table that means let's say over here we are at uh for let's

99
00:04:58,230 --> 00:04:59,760
say we have traversed till four.

100
00:04:59,760 --> 00:05:01,500
Now let me just write that over here.

101
00:05:01,500 --> 00:05:03,270
What would be the hash table at that point?

102
00:05:03,270 --> 00:05:08,160
It would be two one and three two.

103
00:05:08,160 --> 00:05:08,580
Right.

104
00:05:08,580 --> 00:05:09,690
And then we are at four.

105
00:05:09,690 --> 00:05:11,640
So array of I is four.

106
00:05:11,640 --> 00:05:15,510
Now at that point the needed value will be equal to.

107
00:05:16,170 --> 00:05:18,990
Four seven minus four, which is equal to three.

108
00:05:18,990 --> 00:05:19,350
Right.

109
00:05:19,350 --> 00:05:22,140
And we will see that it's already there in the hash table.

110
00:05:22,140 --> 00:05:22,530
It's there.

111
00:05:22,530 --> 00:05:22,890
Right.

112
00:05:22,890 --> 00:05:25,890
So we know that it already occurred.

113
00:05:25,890 --> 00:05:28,050
So that's the case which we are writing over here.

114
00:05:28,050 --> 00:05:30,660
At this point we need to return the indices.

115
00:05:30,660 --> 00:05:35,310
So one index will be I which is the index of four in this at this point.

116
00:05:35,310 --> 00:05:41,400
And the other case would be the value at the uh key of three in the hash table.

117
00:05:41,400 --> 00:05:41,670
Right.

118
00:05:41,670 --> 00:05:45,420
So we need to take the value by passing in the key.

119
00:05:45,420 --> 00:05:47,340
So let's do that hash table.

120
00:05:47,580 --> 00:05:51,030
And we are going to pass in the value as needed value.

121
00:05:52,950 --> 00:05:55,110
So we are going to return this at this point.

122
00:05:55,110 --> 00:05:57,090
And there we have our solution.

123
00:05:57,090 --> 00:06:03,090
Now the only thing that remains is if we come out of this for loop without returning anything, that

124
00:06:03,090 --> 00:06:08,520
means we were not able to find a pair that adds up to the target value, and we will return the empty

125
00:06:08,520 --> 00:06:08,880
array.

126
00:06:08,880 --> 00:06:10,680
And there we have our solution.

127
00:06:10,680 --> 00:06:15,450
Now let's go ahead and test whether our solution is working for this.

128
00:06:15,450 --> 00:06:23,010
Let me say array is equal to for example one minus two 345.

129
00:06:23,010 --> 00:06:24,960
And let's say target value.

130
00:06:25,800 --> 00:06:27,990
Is equal to, let's say three.

131
00:06:28,020 --> 00:06:28,530
Okay.

132
00:06:28,530 --> 00:06:33,120
Now let's console log what we get when we call our function.

133
00:06:33,120 --> 00:06:35,700
So we have find indices some given.

134
00:06:35,700 --> 00:06:38,790
And we are passing the array and the target value.

135
00:06:39,930 --> 00:06:41,370
Now let's see what happens.

136
00:06:42,820 --> 00:06:43,930
So I'm running this.

137
00:06:44,620 --> 00:06:49,690
Now when we run this, you can see that we get the array four comma one as output.

138
00:06:49,690 --> 00:06:53,200
So index four is 01234 which is five.

139
00:06:53,200 --> 00:06:55,330
So value five is at index four.

140
00:06:55,330 --> 00:07:01,120
And at index one we have minus two right 015 plus minus two gives us three.

141
00:07:01,120 --> 00:07:03,760
So yes our algorithm is working.

142
00:07:03,760 --> 00:07:06,190
Now what if I pass an empty array.

143
00:07:08,700 --> 00:07:09,990
And let's run it.

144
00:07:09,990 --> 00:07:12,660
So I get an empty array as output so it works.

145
00:07:12,660 --> 00:07:17,370
If it's a single element array, again I get an empty array which works.

146
00:07:17,370 --> 00:07:22,440
And let's say I have three comma nine and the target value is also 12.

147
00:07:22,470 --> 00:07:24,660
If I run it, I'll get the answer as one comma two.

148
00:07:24,690 --> 00:07:26,940
So yes, our algorithm is working.

149
00:07:26,940 --> 00:07:33,180
Now let's take a relook at the code that we have written to analyze in greater depth what is happening.