1
00:00:00,400 --> 00:00:01,360
Welcome back.

2
00:00:01,360 --> 00:00:04,330
Let's now try to think how we can solve this question.

3
00:00:04,330 --> 00:00:06,130
For this let's take a sample array.

4
00:00:06,130 --> 00:00:08,500
So let's say this is the array which is given to us.

5
00:00:08,500 --> 00:00:10,300
So let's write the indices.

6
00:00:10,300 --> 00:00:12,820
So we have zero up to 11.

7
00:00:12,820 --> 00:00:13,240
All right.

8
00:00:13,240 --> 00:00:16,600
And let's say the target which is given to us is equal to five.

9
00:00:16,600 --> 00:00:18,670
So we can see that we have five over here.

10
00:00:18,670 --> 00:00:20,050
And then it goes on till here.

11
00:00:20,050 --> 00:00:22,540
So the output should be four comma nine.

12
00:00:22,540 --> 00:00:25,180
So let's try to see how we can do this.

13
00:00:25,180 --> 00:00:27,970
Now again some of the things that we have to note over here.

14
00:00:27,970 --> 00:00:30,310
First of all the array is sorted.

15
00:00:30,310 --> 00:00:32,950
So it's sorted in non-decreasing order.

16
00:00:32,950 --> 00:00:40,060
And then we also have to write a solution which runs in time complexity of O of log n as per the question.

17
00:00:40,060 --> 00:00:43,480
So these are indications that we have to use binary search over here.

18
00:00:43,480 --> 00:00:49,180
Now we will see how we will use a slightly modified version of binary search.

19
00:00:49,180 --> 00:00:55,270
And we will use binary search two times for first time to find the left extreme, which is four over

20
00:00:55,270 --> 00:01:00,040
here, and the second time to find the right extreme which is nine over here.

21
00:01:00,040 --> 00:01:04,840
So we will use a modified version of binary search and we will use it two times.

22
00:01:04,840 --> 00:01:06,310
So let's just walk through it.

23
00:01:06,310 --> 00:01:08,050
So that's the best way to understand this.

24
00:01:08,050 --> 00:01:13,570
So we are again going to have a left and right pointer which is pointing to the first and the last index

25
00:01:13,570 --> 00:01:15,940
as we have in the case of binary search.

26
00:01:15,940 --> 00:01:22,270
Now we are going to find the middle which is equal to floor of zero plus 11 divided by two which is

27
00:01:22,270 --> 00:01:23,110
equal to five.

28
00:01:23,110 --> 00:01:25,510
So middle is pointing to index five.

29
00:01:25,510 --> 00:01:33,010
Now when we see that the target value is equal to the value at this index middle index, if it was not

30
00:01:33,010 --> 00:01:36,730
equal, then we would have just proceeded with binary search as usual.

31
00:01:36,730 --> 00:01:42,670
But the modification or the slight difference to the binary search happens when we find that the target

32
00:01:42,670 --> 00:01:45,370
value is equal to the value at the middle index.

33
00:01:45,370 --> 00:01:49,570
So it's from there that we are making some modifications to the binary search.

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

35
00:01:50,080 --> 00:01:54,820
So we find that the target is equal to the value at the middle index.

36
00:01:54,820 --> 00:01:57,070
So let's go ahead and modify binary search.

37
00:01:57,070 --> 00:01:58,390
So let's see what we have to do.

38
00:01:58,390 --> 00:02:02,770
So we have seen that the value at the middle index is equal to target.

39
00:02:02,770 --> 00:02:08,950
Now let's first check if middle at this point is equal to zero which is the left most index.

40
00:02:08,950 --> 00:02:12,400
If that is the case then we have found the left extreme.

41
00:02:12,400 --> 00:02:16,300
And that would be zero itself because we cannot go any more left right.

42
00:02:16,300 --> 00:02:21,610
So if middle at this point, when middle was the value at middle was equal to target, if middle was

43
00:02:21,610 --> 00:02:24,730
pointing to index zero, then we don't have anything to its left.

44
00:02:24,730 --> 00:02:27,880
And that's why we can say left extreme is equal to zero.

45
00:02:27,880 --> 00:02:31,690
Now if this is not the case then we are currently over here.

46
00:02:31,690 --> 00:02:33,640
Middle is pointing to this index right.

47
00:02:33,640 --> 00:02:35,710
We're going to check the previous value.

48
00:02:35,710 --> 00:02:37,630
So the value at index four.

49
00:02:37,630 --> 00:02:41,260
So we are going to check if the previous value is equal to target.

50
00:02:41,260 --> 00:02:47,020
Now if that is the case then we have to repeat the binary search on the left part.

51
00:02:47,020 --> 00:02:49,990
Because we have not yet found the left extreme.

52
00:02:50,260 --> 00:02:56,290
And repeating on the left part means nothing but setting right to be equal to middle minus one.

53
00:02:56,290 --> 00:03:01,660
And then we proceed, whether recursively or iteratively, we are again going to go with the same logic.

54
00:03:01,660 --> 00:03:02,080
All right.

55
00:03:02,110 --> 00:03:08,080
Now if this is not the case, that is if the previous value is not equal to target, then we can say

56
00:03:08,080 --> 00:03:11,620
that we have found the left extreme and that would be equal to middle.

57
00:03:11,620 --> 00:03:16,960
For example, if middle was pointing to four, then we see that the previous value is not equal to target.

58
00:03:16,960 --> 00:03:21,610
That means that this this index over here itself would be the left extreme.

59
00:03:21,610 --> 00:03:25,510
So this is the algorithm that we will use to find the left extreme.

60
00:03:25,510 --> 00:03:29,980
And we will have a slightly modified version of this to find the right extreme.

61
00:03:29,980 --> 00:03:31,810
So let's go ahead and walk through the code.

62
00:03:31,810 --> 00:03:34,030
So middle is now pointing to index five.

63
00:03:34,030 --> 00:03:37,300
And we see that value at middle is equal to target right.

64
00:03:37,300 --> 00:03:39,790
And we see that middle is not equal to zero.

65
00:03:39,790 --> 00:03:42,010
So we are going to check the previous value.

66
00:03:42,010 --> 00:03:45,520
And we see that the previous value in fact is equal to target.

67
00:03:45,520 --> 00:03:49,510
Therefore we are going to repeat on the left part which means nothing.

68
00:03:49,510 --> 00:03:52,660
But setting right is equal to middle minus one.

69
00:03:52,660 --> 00:03:53,440
So let's do that.

70
00:03:53,440 --> 00:03:56,350
So right is going to point to index four at this point.

71
00:03:56,350 --> 00:04:01,330
And again we continue we are going to find the new middle which is going to be equal to zero plus four

72
00:04:01,330 --> 00:04:03,490
divided by two which is equal to two.

73
00:04:03,490 --> 00:04:06,040
So middle is going to point to two at this point.

74
00:04:06,040 --> 00:04:09,730
Again we are going to check is the value at middle equal to target.

75
00:04:09,730 --> 00:04:11,680
So let's try to see that.

76
00:04:11,680 --> 00:04:15,010
We see that the value over here is three and the target is five.

77
00:04:15,010 --> 00:04:16,510
So it's not equal right.

78
00:04:16,510 --> 00:04:22,330
And then because it's not equal we are doing the same thing as we would do in binary search.

79
00:04:22,330 --> 00:04:26,800
The modification only happens when the value at middle is equal to target.

80
00:04:26,800 --> 00:04:29,530
So over here the value at middle is not equal to target.

81
00:04:29,530 --> 00:04:35,500
So as in binary search we would just move left to middle plus one because target is greater than the

82
00:04:35,500 --> 00:04:37,030
value at middle right.

83
00:04:37,030 --> 00:04:38,470
So target is greater than three.

84
00:04:38,470 --> 00:04:42,610
So let's move left to middle plus one as we would do in binary search.

85
00:04:42,610 --> 00:04:44,710
And then we again find the new middle.

86
00:04:44,710 --> 00:04:48,400
So the new new middle is going to be three plus four divided by two.

87
00:04:48,400 --> 00:04:50,860
And then floor it which is equal to three itself.

88
00:04:50,860 --> 00:04:51,070
Right.

89
00:04:51,070 --> 00:04:52,690
So middle is going to point to three.

90
00:04:52,690 --> 00:04:57,190
And then we are going to check the value over here the value is four and the target is five.

91
00:04:57,190 --> 00:04:59,920
So we see that target is greater than four.

92
00:05:00,060 --> 00:05:01,140
Or the value over here.

93
00:05:01,140 --> 00:05:03,240
Hence we're going to move left.

94
00:05:03,240 --> 00:05:06,360
The left pointer is again going to be moved to middle plus one.

95
00:05:06,360 --> 00:05:08,760
So that is typical vanilla binary search right.

96
00:05:08,760 --> 00:05:11,670
So again we move the left pointer to middle plus one.

97
00:05:11,670 --> 00:05:13,920
And we are going to calculate the new middle.

98
00:05:13,920 --> 00:05:17,340
Now the left and the right pointer is equal to four.

99
00:05:17,340 --> 00:05:21,120
So middle is going to be four plus four divided by two which is four itself.

100
00:05:21,120 --> 00:05:25,230
Now we see that the value at middle is equal to target which is five.

101
00:05:25,230 --> 00:05:29,850
And we see that middle is not equal to zero because middle is equal to four.

102
00:05:29,850 --> 00:05:35,580
And when we look at the previous value we see that the previous value is not equal to target right.

103
00:05:35,580 --> 00:05:36,900
The previous value is four.

104
00:05:36,900 --> 00:05:42,690
Therefore we have found the left extreme and we can just return four which is the left extreme which

105
00:05:42,690 --> 00:05:43,830
is this index over here.

106
00:05:43,830 --> 00:05:46,710
So this is how the modified binary search works.

107
00:05:46,710 --> 00:05:51,690
So we have called the binary search modified binary search to find the left extreme.

108
00:05:51,690 --> 00:05:54,270
At this point let's quickly recap what we have done.

109
00:05:54,270 --> 00:06:00,810
So till we find the value at the middle index to be equal to target, it's the same thing as binary

110
00:06:00,810 --> 00:06:01,200
search.

111
00:06:01,200 --> 00:06:04,920
So we are going to have a left index and we are having a right pointer.

112
00:06:04,920 --> 00:06:05,790
We find the middle.

113
00:06:05,790 --> 00:06:12,450
And if the value is equal to the target then we are going to check whether middle is zero or whether

114
00:06:12,450 --> 00:06:14,220
the previous value is equal to target.

115
00:06:14,220 --> 00:06:16,920
So if middle is zero, then the left extreme is equal to zero.

116
00:06:16,920 --> 00:06:22,530
But if middle is not equal to zero, and if the previous value is equal to the target, then we are

117
00:06:22,530 --> 00:06:24,660
going to repeat on the left part.

118
00:06:24,660 --> 00:06:27,510
So this is the repetition of the binary search on the left part.

119
00:06:27,510 --> 00:06:30,870
And we do that by setting right is equal to middle minus one.

120
00:06:30,870 --> 00:06:37,440
And then this keeps on happening and it will stop either when middle is equal to zero or when the previous

121
00:06:37,440 --> 00:06:39,240
value is not equal to target.

122
00:06:39,240 --> 00:06:42,420
In either case we would have found the left left extreme.

123
00:06:42,420 --> 00:06:44,550
So this is how we find the left extreme.

124
00:06:44,550 --> 00:06:51,090
Now let's proceed and take a look at how we can use binary search one more time to find the right extreme.

125
00:06:51,090 --> 00:06:52,110
So let's go ahead.

126
00:06:52,110 --> 00:06:53,250
And again we start.

127
00:06:53,250 --> 00:06:57,030
We have the left index and the left pointer and the right pointer.

128
00:06:57,030 --> 00:06:59,400
At the two extremes we find the middle.

129
00:06:59,400 --> 00:07:01,110
So zero plus 11 by two.

130
00:07:01,110 --> 00:07:02,640
When we floor it we get five.

131
00:07:02,640 --> 00:07:04,350
So this is the middle at this point.

132
00:07:04,350 --> 00:07:07,440
Now we see that the value at middle is equal to target.

133
00:07:07,440 --> 00:07:10,950
So at this point we have some modification from the binary search.

134
00:07:10,950 --> 00:07:15,600
Now if it was not equal we would have just proceeded normally as in the case of binary search.

135
00:07:15,600 --> 00:07:18,840
That is we would move the left pointer or the right pointer.

136
00:07:18,840 --> 00:07:24,090
So if the target would have been greater than the middle value, then we would have moved the left pointer.

137
00:07:24,090 --> 00:07:27,540
And if the target is less than the value at middle, we would have moved the right pointer.

138
00:07:27,540 --> 00:07:29,430
So that is normal binary search.

139
00:07:29,430 --> 00:07:33,360
Now let's proceed over here we see that value at middle is equal to target.

140
00:07:33,360 --> 00:07:39,480
Therefore we will check if middle is equal to length minus one which is the last index.

141
00:07:39,480 --> 00:07:41,610
We see that that's not the case right.

142
00:07:41,610 --> 00:07:44,520
Because if this is the case we can't move any more further.

143
00:07:44,520 --> 00:07:45,000
Right.

144
00:07:45,000 --> 00:07:50,010
And we would have found our right extreme which would be nothing but length minus one or middle.

145
00:07:50,010 --> 00:07:54,150
Now, if this is not the case, we are going to check the next value.

146
00:07:54,150 --> 00:07:54,480
All right.

147
00:07:54,480 --> 00:07:57,510
So we will check if the next value is equal to target.

148
00:07:57,510 --> 00:08:03,030
If the next value is equal to target then we have to repeat the same process on the right part.

149
00:08:03,030 --> 00:08:05,850
So the right part means towards the right of middle right.

150
00:08:05,850 --> 00:08:10,920
And repeating on the right part means nothing, but setting left is equal to middle plus one.

151
00:08:10,920 --> 00:08:11,310
All right.

152
00:08:11,310 --> 00:08:16,830
Now if this is not the case, that is, if the next value is not equal to target, then we would have

153
00:08:16,830 --> 00:08:18,270
found the right extreme.

154
00:08:18,270 --> 00:08:20,850
And the right extreme is just equal to middle.

155
00:08:20,850 --> 00:08:22,980
So this is how the algorithm works.

156
00:08:22,980 --> 00:08:28,620
You can see that the algorithm for the right part is pretty similar to what we have seen for the left

157
00:08:28,620 --> 00:08:28,860
part.

158
00:08:28,860 --> 00:08:29,190
Right.

159
00:08:29,190 --> 00:08:33,450
The only difference is over here we are checking whether middle is the right most index.

160
00:08:33,450 --> 00:08:35,400
And over here we were checking for zero.

161
00:08:35,400 --> 00:08:39,420
And then for finding the left extreme we check the previous value.

162
00:08:39,420 --> 00:08:41,760
But over here we are checking the next value.

163
00:08:41,760 --> 00:08:42,630
So that's the difference.

164
00:08:42,630 --> 00:08:44,880
All right so let's just walk through the code over here.

165
00:08:44,880 --> 00:08:46,110
Walk through the algorithm.

166
00:08:46,440 --> 00:08:49,050
Now at this point middle is pointing to five.

167
00:08:49,050 --> 00:08:51,870
And we have seen that value at middle is equal to target.

168
00:08:51,870 --> 00:08:55,350
So we are checking whether middle is length minus one which is 11.

169
00:08:55,350 --> 00:08:57,000
No that's not equal right.

170
00:08:57,000 --> 00:08:58,950
So we are going to check the next value.

171
00:08:58,950 --> 00:09:03,180
So the next value we can see that that next value is also equal to target.

172
00:09:03,180 --> 00:09:06,420
Therefore we have to repeat on the right part.

173
00:09:06,450 --> 00:09:10,740
Now repeating on the right part means setting left is equal to middle plus one.

174
00:09:10,740 --> 00:09:11,250
All right.

175
00:09:11,250 --> 00:09:14,280
So left is pointing to six and right is at 11.

176
00:09:14,280 --> 00:09:21,600
We are going to calculate the new middle which is six plus 11 which is 1717 by 217 by two gives us 8.5.

177
00:09:21,600 --> 00:09:23,970
And then when we floor it we get eight right.

178
00:09:23,970 --> 00:09:24,840
So we get eight.

179
00:09:24,840 --> 00:09:27,120
So middle is pointing to index eight.

180
00:09:27,120 --> 00:09:30,810
And again we are going to check is the value at middle equal to target.

181
00:09:30,810 --> 00:09:33,240
Now at this point we see that it is equal.

182
00:09:33,240 --> 00:09:36,300
If it was not equal then it's simple binary search.

183
00:09:36,300 --> 00:09:36,480
Right.

184
00:09:36,480 --> 00:09:39,360
We would move the left or the right pointer accordingly.

185
00:09:39,360 --> 00:09:44,790
But over here because it is equal we are going to check is middle equal to length minus one which is

186
00:09:44,790 --> 00:09:45,210
11.

187
00:09:45,210 --> 00:09:46,320
No middle is eight.

188
00:09:46,320 --> 00:09:47,850
And that's not equal to 11.

189
00:09:47,850 --> 00:09:52,200
So we are going to check the next value is the next value equal to the target.

190
00:09:52,200 --> 00:09:54,540
Over here we can see that the next value is five.

191
00:09:54,540 --> 00:09:56,550
And yes we see that it's equal.

192
00:09:56,550 --> 00:09:59,790
Therefore we have to repeat on the right part which is.

193
00:09:59,990 --> 00:10:03,050
We are going to set left is equal to middle plus one.

194
00:10:03,050 --> 00:10:06,260
So we have left at nine and right at 11.

195
00:10:06,260 --> 00:10:07,130
Again we proceed.

196
00:10:07,130 --> 00:10:12,050
We are going to find the middle value which is nine plus 11 by two which is equal to ten right.

197
00:10:12,050 --> 00:10:13,100
Which that's equal to ten.

198
00:10:13,100 --> 00:10:15,320
So middle is pointing at index ten.

199
00:10:15,320 --> 00:10:18,710
Again we are going to check is the value at middle equal to target.

200
00:10:18,740 --> 00:10:20,300
No it's not equal right.

201
00:10:20,300 --> 00:10:21,860
Because it's not equal.

202
00:10:21,860 --> 00:10:24,800
That is this seven over here is not equal to target.

203
00:10:24,800 --> 00:10:27,920
Therefore we are going to check is it greater or less than.

204
00:10:27,920 --> 00:10:28,220
Right.

205
00:10:28,220 --> 00:10:30,980
So we can see that target is actually less than seven.

206
00:10:30,980 --> 00:10:33,470
So target is less than equal to seven.

207
00:10:33,470 --> 00:10:37,670
Therefore we have to move the right pointer to middle minus one.

208
00:10:37,670 --> 00:10:39,050
So that is binary search right.

209
00:10:39,050 --> 00:10:41,180
So that is how we implemented binary search.

210
00:10:41,180 --> 00:10:44,060
So let's move the right pointer to middle minus one.

211
00:10:44,060 --> 00:10:48,020
So you can see the left and the right pointer now are pointing to nine.

212
00:10:48,020 --> 00:10:52,130
And middle is going to be nine plus nine by two which is nine itself.

213
00:10:52,130 --> 00:10:55,880
Now again we check is the value at middle equal to target.

214
00:10:55,880 --> 00:10:57,050
Yes it's equal right.

215
00:10:57,050 --> 00:10:58,760
Because this is five and this is five.

216
00:10:58,760 --> 00:11:01,670
Now we check is middle equal to length minus one.

217
00:11:01,670 --> 00:11:02,780
Is it the last index.

218
00:11:02,780 --> 00:11:03,830
No it's not.

219
00:11:03,830 --> 00:11:06,650
Now is the next value equal to target.

220
00:11:06,650 --> 00:11:10,640
No the next value is not equal to target because the next value over here is seven.

221
00:11:10,640 --> 00:11:11,000
Right.

222
00:11:11,000 --> 00:11:17,480
Therefore we come over here and we can see that we have found the right extreme which is equal to nine.

223
00:11:17,480 --> 00:11:19,760
So the right extreme is equal to nine.

224
00:11:19,760 --> 00:11:21,740
So we have found four and nine.

225
00:11:21,740 --> 00:11:25,280
And we can just return four comma nine which are the extremes.

226
00:11:25,280 --> 00:11:28,070
So this is how we are going to implement the solution.

227
00:11:28,070 --> 00:11:33,650
You can see that the time complexity of this solution is going to be two times log n.

228
00:11:33,650 --> 00:11:35,780
Why is that so O of two times log n.

229
00:11:35,780 --> 00:11:38,720
Because we are calling two times the binary search right?

230
00:11:38,720 --> 00:11:43,430
One time to find the left extreme, and then one more time to find the right extreme.

231
00:11:43,430 --> 00:11:44,660
Now two is a constant.

232
00:11:44,660 --> 00:11:46,310
So we can just avoid this.

233
00:11:46,310 --> 00:11:51,920
And we can say that the time complexity of this solution is O of log n, and the space complexity is

234
00:11:51,920 --> 00:11:53,270
going to be O of one.

235
00:11:53,270 --> 00:11:59,990
If we implement this iteratively, and it's going to be O of log n if we implement it recursively because

236
00:11:59,990 --> 00:12:01,100
of the call stack.

237
00:12:01,990 --> 00:12:03,430
Now let's take a look at this.

238
00:12:03,430 --> 00:12:04,210
For example.

239
00:12:04,210 --> 00:12:06,190
Let's say this is the array which is given to us.

240
00:12:06,190 --> 00:12:07,870
So you can see it's all five.

241
00:12:07,870 --> 00:12:09,910
And then the target is also five.

242
00:12:09,910 --> 00:12:15,820
So we make one call on the call stack where the left extreme is zero and the right extreme is seven.

243
00:12:15,820 --> 00:12:18,850
So we are discussing about the recursive implementation of this.

244
00:12:18,850 --> 00:12:24,250
Now the second call would be where we move right to middle minus one.

245
00:12:24,250 --> 00:12:24,430
Right.

246
00:12:24,430 --> 00:12:27,550
Because you can see that the previous value also is equal to five.

247
00:12:27,550 --> 00:12:30,670
So we would move right to middle minus one.

248
00:12:30,670 --> 00:12:32,380
And left will be at zero itself.

249
00:12:32,380 --> 00:12:33,970
So this is the second call right.

250
00:12:33,970 --> 00:12:36,490
Again we find the middle which is going to be one.

251
00:12:36,490 --> 00:12:39,310
And we are seeing that that value is equal to target.

252
00:12:39,310 --> 00:12:42,130
And the previous value is also equal to target.

253
00:12:42,130 --> 00:12:46,150
So again we are going to move right to middle minus one which is over here.

254
00:12:46,150 --> 00:12:48,880
And middle is also going to be pointing to zero.

255
00:12:48,880 --> 00:12:52,330
And at this point we find again that middle is equal to zero.

256
00:12:52,330 --> 00:12:53,770
So we have found the left extreme.

257
00:12:53,770 --> 00:12:59,380
So you can see that we have called the function recursively three times and log of eight.

258
00:12:59,380 --> 00:13:03,460
So we have eight elements over here log of eight is equal to also three right.

259
00:13:03,460 --> 00:13:04,930
So eight is two to the power three.

260
00:13:04,930 --> 00:13:07,510
So log of eight is log of two to the power three.

261
00:13:07,510 --> 00:13:09,190
And this is equal to three right.

262
00:13:09,190 --> 00:13:13,990
So that's why we can say that the call stack takes O of log n space space.

263
00:13:13,990 --> 00:13:18,730
If we implement this solution recursively and the space complexity is going to be O of one.

264
00:13:18,730 --> 00:13:25,090
If we implement this iteratively and the time complexity is O of log n, and yes, we have seen it can

265
00:13:25,090 --> 00:13:28,300
be O of two times log n, but then two is a constant.

266
00:13:28,300 --> 00:13:29,290
So we avoid it.

267
00:13:29,290 --> 00:13:31,720
And we say that the time complexity is O of log.