1
00:00:00,700 --> 00:00:01,630
Hi everyone.

2
00:00:01,630 --> 00:00:05,320
So we have understood the question and we have formulated test cases.

3
00:00:05,320 --> 00:00:09,850
Now let's try to look at the logic or the method by which we can solve this.

4
00:00:09,850 --> 00:00:14,710
Now the first method that we discussed over here is the brute force method, which is very simple to

5
00:00:14,710 --> 00:00:19,000
understand, but probably not the best or the most optimal solution.

6
00:00:19,000 --> 00:00:20,410
Now let's walk through this.

7
00:00:20,410 --> 00:00:20,950
First.

8
00:00:20,950 --> 00:00:27,940
Let's say the given array is 273 minus one four and the target value is equal to two.

9
00:00:27,940 --> 00:00:28,480
All right.

10
00:00:28,480 --> 00:00:32,230
Now let me write the indices of the elements of the given array.

11
00:00:32,230 --> 00:00:34,870
So 0123 and four.

12
00:00:34,870 --> 00:00:37,540
Now initially we initialize.

13
00:00:37,540 --> 00:00:42,880
Let's say we initialize a pointer and let it point to the first element in the given array.

14
00:00:43,180 --> 00:00:46,180
Now naturally what is it that we are trying to do?

15
00:00:46,180 --> 00:00:51,460
We are we will be looking at, we will keep this constant, and we will look at all the other values

16
00:00:51,460 --> 00:00:55,720
and see if there are any two values which add up to the target value.

17
00:00:55,720 --> 00:00:55,990
Right.

18
00:00:55,990 --> 00:00:57,550
So that's the brute force method.

19
00:00:57,550 --> 00:01:05,530
We are just uh, looking at how a normal person would just, uh, without any knowledge about complexity

20
00:01:05,530 --> 00:01:06,670
would try to solve this.

21
00:01:06,670 --> 00:01:12,250
So we would traverse the remaining elements over here, and let's say we have another pointer and let

22
00:01:12,250 --> 00:01:13,330
that be called J.

23
00:01:13,330 --> 00:01:19,750
And we will see whether any element at the ith index and the jth index when we add them, whether we

24
00:01:19,750 --> 00:01:21,220
can get the target value.

25
00:01:21,220 --> 00:01:25,570
So we will check if array at ith index plus array at jth index.

26
00:01:25,570 --> 00:01:30,850
So this is i'th index element and this is the element at the jth index if they add up to the target

27
00:01:30,850 --> 00:01:31,120
value.

28
00:01:31,120 --> 00:01:32,260
So that's what you are checking.

29
00:01:32,260 --> 00:01:37,000
So we will see if two plus seven is 2 or 2 plus three is two etc..

30
00:01:37,000 --> 00:01:39,460
So now checking this is the same.

31
00:01:39,460 --> 00:01:45,070
Another way in which some people may write this is we could also check whether j is equal to the target

32
00:01:45,070 --> 00:01:47,530
value minus the value at the ith index.

33
00:01:47,530 --> 00:01:49,810
Again, this is the value at the jth index.

34
00:01:49,810 --> 00:01:50,080
All right.

35
00:01:50,080 --> 00:01:52,000
So these two are just one.

36
00:01:52,000 --> 00:01:53,050
And the same thing.

37
00:01:53,050 --> 00:01:55,390
It's just two ways of checking the same thing.

38
00:01:55,870 --> 00:01:56,290
All right.

39
00:01:56,290 --> 00:01:58,090
So we have our array over here.

40
00:01:58,090 --> 00:02:00,880
Now let's try to see how this spans out.

41
00:02:00,880 --> 00:02:04,840
So first our index or our pointer is pointing at two.

42
00:02:04,870 --> 00:02:06,040
So I is equal to two.

43
00:02:06,040 --> 00:02:06,400
All right.

44
00:02:06,400 --> 00:02:07,930
So the value of I is two.

45
00:02:07,960 --> 00:02:09,910
Now what's the value that we need.

46
00:02:09,910 --> 00:02:13,990
Two plus something is equal to the target value which is two.

47
00:02:14,020 --> 00:02:18,100
So the needed value is this two minus what we have over here.

48
00:02:18,100 --> 00:02:18,430
Right.

49
00:02:18,430 --> 00:02:23,980
So that's target value minus the value at the ith index or two minus two which is equal to zero because

50
00:02:23,980 --> 00:02:25,840
two plus zero is equal to two.

51
00:02:25,870 --> 00:02:27,220
So we need zero right.

52
00:02:27,220 --> 00:02:32,860
So we are going to traverse the remaining elements which are these elements which we have seen over

53
00:02:32,860 --> 00:02:33,190
here.

54
00:02:33,190 --> 00:02:36,160
And we are going to check whether we have zero over here.

55
00:02:36,160 --> 00:02:40,450
So over here we have seven, we have three, we have minus one and we have four.

56
00:02:40,450 --> 00:02:42,550
So in none of these we have zero.

57
00:02:42,550 --> 00:02:47,140
So definitely there is no solution in which this is part of the solution.

58
00:02:47,140 --> 00:02:50,350
So we change the value of I by changing the pointer.

59
00:02:50,350 --> 00:02:53,380
And we point to the next element which is seven.

60
00:02:53,380 --> 00:02:56,620
So the value at the ith index now is seven.

61
00:02:56,620 --> 00:03:00,880
Now seven plus something is equal to the target value which is two.

62
00:03:00,910 --> 00:03:05,200
So the needed value is equal to two minus seven which is equal to minus five.

63
00:03:05,200 --> 00:03:09,310
So we are going to check the remaining values which is this part over here.

64
00:03:09,310 --> 00:03:13,450
And we will see whether we have minus five in any of these places.

65
00:03:13,450 --> 00:03:16,450
Now notice that we are only checking the remaining values.

66
00:03:16,450 --> 00:03:18,370
We are not checking what came before it.

67
00:03:18,370 --> 00:03:18,850
Right.

68
00:03:19,300 --> 00:03:21,280
We are not checking what is over here now.

69
00:03:21,280 --> 00:03:22,150
Why is that so?

70
00:03:22,150 --> 00:03:27,460
Because if what is over here was a solution, then it's the same.

71
00:03:27,460 --> 00:03:31,720
Writing the solution as two comma 7 or 7 comma two is one and the same.

72
00:03:31,720 --> 00:03:32,020
Right?

73
00:03:32,020 --> 00:03:37,870
So if what came over here was part of the solution, we would have already found it in the previous

74
00:03:37,870 --> 00:03:38,500
iteration.

75
00:03:38,500 --> 00:03:41,800
But because it was not found in the previous iteration.

76
00:03:41,800 --> 00:03:44,230
So we don't need to check this in the next iteration.

77
00:03:44,230 --> 00:03:50,050
So a possible solution can only exist as a pair of seven and one of the remaining elements.

78
00:03:50,050 --> 00:03:52,300
So again we are checking for minus five.

79
00:03:52,300 --> 00:03:58,510
Now we look at the remaining parts and we see that in none of these places we have minus five right.

80
00:03:58,510 --> 00:04:00,940
So again we move the pointer of I.

81
00:04:00,970 --> 00:04:05,830
So it was over here and again we move it to the next one which is three.

82
00:04:05,830 --> 00:04:06,220
Right.

83
00:04:06,220 --> 00:04:08,260
So I at this point is three.

84
00:04:08,260 --> 00:04:11,080
Now the needed value is target value minus three.

85
00:04:11,080 --> 00:04:16,450
Right target value minus the ith value which is equal to minus one at this point.

86
00:04:16,450 --> 00:04:18,160
So we are checking for minus one.

87
00:04:18,160 --> 00:04:20,560
Again we only need to check the remaining parts.

88
00:04:20,560 --> 00:04:22,810
We don't need to check what came before it.

89
00:04:22,810 --> 00:04:29,290
Because again as we've already discussed, if what came before was part of the solution, it would already

90
00:04:29,290 --> 00:04:31,660
have been caught in the previous iterations, right?

91
00:04:31,660 --> 00:04:32,860
Because it was not caught.

92
00:04:32,860 --> 00:04:34,930
So we don't need to care about these values.

93
00:04:34,930 --> 00:04:37,510
We're only going to check only for the remaining parts.

94
00:04:37,510 --> 00:04:40,630
Now the next value is minus one, right.

95
00:04:40,630 --> 00:04:43,690
And when we see that three plus minus one that's two.

96
00:04:43,720 --> 00:04:45,130
That's the needed value.

97
00:04:45,130 --> 00:04:45,490
Right.

98
00:04:45,490 --> 00:04:49,960
We were checking for minus one and we saw that minus one is there in the next value.

99
00:04:49,960 --> 00:04:53,470
So we got our answer three plus minus one is equal to two.

100
00:04:53,470 --> 00:04:59,530
And as the question asks us to return the indices don't return three and minus one rather than return

101
00:04:59,530 --> 00:05:00,280
the indices two.

102
00:05:00,610 --> 00:05:01,480
And three.

103
00:05:01,480 --> 00:05:03,310
And that is our answer.

104
00:05:03,670 --> 00:05:05,380
The answer is two comma three.

105
00:05:05,590 --> 00:05:06,160
All right.

106
00:05:06,190 --> 00:05:11,950
Now let's take a look at the complexity at the space and time complexity of this solution.

107
00:05:11,950 --> 00:05:13,270
The brute force solution.

108
00:05:13,300 --> 00:05:19,480
Now over here you can see that with I with the pointer I we are traversing the array once.

109
00:05:19,480 --> 00:05:26,590
So if in the array there are n elements we would be doing n operations to traverse the array once with

110
00:05:26,590 --> 00:05:27,670
the pointer I.

111
00:05:27,760 --> 00:05:28,450
All right.

112
00:05:28,480 --> 00:05:36,460
Now we can also see that at every iteration over here that is for every value of I we are again traversing

113
00:05:36,460 --> 00:05:36,790
the array.

114
00:05:36,790 --> 00:05:36,970
Right.

115
00:05:36,970 --> 00:05:42,520
So again we have seen that I is traversing at this point I was I was pointing to the value two.

116
00:05:42,520 --> 00:05:45,700
And at this point it was pointing to the value seven.

117
00:05:45,700 --> 00:05:48,610
At this point it was pointing to the index with the value three.

118
00:05:48,610 --> 00:05:48,850
Okay.

119
00:05:48,850 --> 00:05:52,360
So it's pointing at the indices with the value two, seven, three, etc..

120
00:05:52,360 --> 00:05:55,990
So we were traversing the array by changing this pointer.

121
00:05:56,110 --> 00:05:59,530
Now at each I we are again traversing the array.

122
00:05:59,530 --> 00:06:02,830
So that's what we did with the j pointer over here.

123
00:06:02,830 --> 00:06:05,470
And so this is another n iteration.

124
00:06:05,470 --> 00:06:09,790
So for every iteration over here and again we have n iterations over here.

125
00:06:09,790 --> 00:06:14,530
For every n every one of these iterations we are doing n iterations again.

126
00:06:14,530 --> 00:06:14,860
Right.

127
00:06:14,860 --> 00:06:21,610
So that's why the time complexity of this solution is o of n into n, which is O of n square.

128
00:06:21,610 --> 00:06:26,350
Now it's true that we are traversing only n minus one operations over here.

129
00:06:26,350 --> 00:06:33,280
And when I was pointing to the value to the index one and it had the value seven, we were doing only

130
00:06:33,280 --> 00:06:35,470
n minus two iterations over here.

131
00:06:35,470 --> 00:06:42,010
But then we just need to know the trend right as the time for running the algorithm.

132
00:06:42,010 --> 00:06:44,530
We are we are actually concerned with that, right?

133
00:06:44,530 --> 00:06:47,020
We are concerned with the larger picture.

134
00:06:47,020 --> 00:06:53,980
So that's why we are not exactly taking it as n minus one, n minus two, etc. in general, it's n iterations

135
00:06:53,980 --> 00:06:59,170
for every iteration in the previous um traversing of the array.

136
00:06:59,170 --> 00:07:03,700
So that's why the time complexity of this solution is O of n square.

137
00:07:03,700 --> 00:07:06,520
Now what about the space complexity of the solution?

138
00:07:06,520 --> 00:07:10,750
We can see that we are not storing anything extra, right?

139
00:07:10,750 --> 00:07:14,170
We are not creating a new array or or using up space.

140
00:07:14,170 --> 00:07:21,610
So the space complexity is O of one which is which is same as saying it runs in constant space.

141
00:07:21,610 --> 00:07:26,260
So the time complexity is O of n square and the space is O of one.

142
00:07:26,260 --> 00:07:31,240
Now O of n square is not a good time complexity right now.

143
00:07:31,240 --> 00:07:35,260
Let's see in the next video whether we can do better than this.

144
00:07:35,260 --> 00:07:42,490
Now a hint that we can take away from this is we can improve the time complexity by using more space.

145
00:07:42,490 --> 00:07:46,270
And we will see how to do that with the hash table in the next video.