1
00:00:00,470 --> 00:00:01,520
Welcome back.

2
00:00:01,550 --> 00:00:08,120
Let's now go ahead and write the iterative solution to find the range of the target value in the array

3
00:00:08,120 --> 00:00:09,230
which is given to us.

4
00:00:09,230 --> 00:00:13,940
So let's call this function search for range iterative.

5
00:00:15,450 --> 00:00:18,000
And this function is going to take in the array.

6
00:00:19,300 --> 00:00:20,710
And the target value.

7
00:00:21,780 --> 00:00:22,230
All right.

8
00:00:22,230 --> 00:00:26,850
Now, once we are inside this function, we are going to have two variables left.

9
00:00:26,850 --> 00:00:27,630
Extreme.

10
00:00:28,670 --> 00:00:35,030
And right extreme, and let this be equal to what we get back from two other functions so left extreme

11
00:00:35,030 --> 00:00:36,500
and right extreme respectively.

12
00:00:36,500 --> 00:00:41,870
So left extreme is going to be equal to what we get from find left extreme function.

13
00:00:43,680 --> 00:00:44,010
All right.

14
00:00:44,010 --> 00:00:47,820
And this function also is going to take in the array and the target value.

15
00:00:47,820 --> 00:00:53,850
And right extreme is going to be what we get back from the find right extreme function.

16
00:00:57,700 --> 00:01:01,330
And this function also takes in the array and the target value.

17
00:01:01,960 --> 00:01:04,510
And then we are just going to return an array.

18
00:01:05,370 --> 00:01:10,350
Where the first value is left extreme and the second value is right extreme.

19
00:01:11,260 --> 00:01:11,620
All right.

20
00:01:11,620 --> 00:01:13,780
So this is how we will approach this question.

21
00:01:13,780 --> 00:01:18,760
Now we need two functions over here because the pointers are moving in different directions when we

22
00:01:18,760 --> 00:01:20,860
want to find left extreme and right extreme.

23
00:01:20,860 --> 00:01:21,640
So that's why.

24
00:01:21,640 --> 00:01:24,700
So we could write it out in a big single function.

25
00:01:24,700 --> 00:01:29,740
But this is just to break the break the code into different parts and make it more readable.

26
00:01:29,740 --> 00:01:32,860
So let's go ahead and write the find left extreme function first.

27
00:01:32,860 --> 00:01:37,450
So we have const find left extreme is equal to function.

28
00:01:38,960 --> 00:01:42,350
And this function takes in the array and the target value.

29
00:01:43,130 --> 00:01:49,880
Now once we are inside it, let's say left is equal to zero and let right be equal to the right most

30
00:01:49,880 --> 00:01:53,060
index, which is array dot length minus one.

31
00:01:53,060 --> 00:01:55,520
And let's initialize the middle variable.

32
00:01:55,910 --> 00:01:56,360
All right.

33
00:01:56,390 --> 00:01:58,130
Now we are going to have a while loop.

34
00:01:58,130 --> 00:02:03,290
And this will keep looping as long as left is less than right less than equal to right.

35
00:02:03,290 --> 00:02:08,390
So this is pretty much similar to how we implemented the binary search iteratively.

36
00:02:08,390 --> 00:02:11,360
So once we are inside the while loop we will calculate middle.

37
00:02:11,360 --> 00:02:14,810
So middle is going to be equal to math dot floor.

38
00:02:15,820 --> 00:02:19,810
Left plus right divided by two.

39
00:02:20,640 --> 00:02:25,650
And then we will check if target is equal to array at middle.

40
00:02:28,680 --> 00:02:29,130
Now.

41
00:02:29,130 --> 00:02:32,850
If it is equal, we will make some modifications to the binary search.

42
00:02:32,850 --> 00:02:35,010
So over here we have some modifications.

43
00:02:36,390 --> 00:02:37,710
Compared to binary search.

44
00:02:37,710 --> 00:02:37,980
All right.

45
00:02:37,980 --> 00:02:39,930
So modified binary search.

46
00:02:41,830 --> 00:02:44,380
Now, if it is not equal, then we just proceed, right?

47
00:02:44,380 --> 00:02:51,310
So if if target is not equal to right middle then we are going to check if target is less than right

48
00:02:51,310 --> 00:02:51,820
middle.

49
00:02:53,060 --> 00:02:59,330
And if that is the case, then we only have to look towards the left part of the middle index so we

50
00:02:59,330 --> 00:03:02,720
can say right is equal to middle minus one.

51
00:03:03,080 --> 00:03:08,060
And if this is not the case, it means that target is greater than right middle.

52
00:03:08,060 --> 00:03:13,220
And we can just say left is equal to middle plus one because we only want to look towards the right

53
00:03:13,220 --> 00:03:13,940
of middle.

54
00:03:13,970 --> 00:03:16,280
Now once we are out of this while loop.

55
00:03:16,280 --> 00:03:21,920
And if we were not able to return anything over here, we will just return minus one, which means that

56
00:03:21,920 --> 00:03:24,680
the target value is not there in our array.

57
00:03:24,830 --> 00:03:25,340
All right.

58
00:03:25,370 --> 00:03:26,360
Now let's proceed.

59
00:03:26,360 --> 00:03:29,390
So if target is equal to array middle let's complete this part.

60
00:03:29,420 --> 00:03:33,140
We have to check if middle is equal to zero right.

61
00:03:33,140 --> 00:03:36,320
If middle is equal to zero then there is nothing before it.

62
00:03:36,320 --> 00:03:41,660
And if array at middle is equal to target, that means we have found the left most extreme.

63
00:03:41,660 --> 00:03:44,150
So in that case we can just return zero.

64
00:03:44,150 --> 00:03:46,580
So the left extreme is going to be equal to zero.

65
00:03:46,610 --> 00:03:47,810
Now let's proceed.

66
00:03:47,810 --> 00:03:54,350
If this is not the case then we will just check if the previous value that is if array at middle minus

67
00:03:54,350 --> 00:03:54,830
one.

68
00:03:55,960 --> 00:03:58,270
Is equal to r, a is equal to target.

69
00:03:59,660 --> 00:03:59,960
All right.

70
00:03:59,960 --> 00:04:05,570
So if the previous value is equal to target then we have to look towards the left part.

71
00:04:05,570 --> 00:04:09,140
Which means we have to set right equal to middle minus one.

72
00:04:09,140 --> 00:04:12,200
And then we keep looping again as long as this is true.

73
00:04:12,290 --> 00:04:18,560
Now if this is not the case that is if the previous value is not equal to target, then also we have

74
00:04:18,560 --> 00:04:24,860
found the left extreme and we can just return middle, which will be the left extreme because the previous

75
00:04:24,860 --> 00:04:26,570
value is not equal to target.

76
00:04:26,570 --> 00:04:29,450
And we know that the array which is given to us is sorted.

77
00:04:29,450 --> 00:04:32,360
So this is how we will find the left extreme.

78
00:04:32,360 --> 00:04:37,400
Now let's go ahead and write the right extreme function as well which is find right extreme.

79
00:04:37,400 --> 00:04:39,110
So let's write it over here.

80
00:04:40,020 --> 00:04:43,860
Const find right extreme is equal to function.

81
00:04:46,880 --> 00:04:50,480
And this function is going to take in the array and the target value.

82
00:04:51,400 --> 00:04:58,270
Now, once inside the function, let's say let left is equal to zero and let right is equal to array

83
00:04:58,270 --> 00:05:00,700
dot length minus one.

84
00:05:00,790 --> 00:05:03,610
And we initialize the middle variable.

85
00:05:03,610 --> 00:05:07,450
So let middle and we'll have our while loop.

86
00:05:07,450 --> 00:05:11,110
And this will keep looping as long as left is less than equal to right.

87
00:05:11,110 --> 00:05:12,970
So this is similar to binary search.

88
00:05:12,970 --> 00:05:17,050
Now once inside the while loop we will calculate middle which is math dot floor.

89
00:05:18,490 --> 00:05:22,960
Left plus right divided by two.

90
00:05:23,590 --> 00:05:29,410
And then once we have middle, we are going to check if target is equal to array at middle.

91
00:05:31,290 --> 00:05:36,480
So if it is equal, then we will have some modifications over here compared to binary search.

92
00:05:36,480 --> 00:05:37,080
Alright.

93
00:05:37,440 --> 00:05:42,540
Now if it is not equal then we are going to check if target less than array at middle.

94
00:05:43,440 --> 00:05:49,050
If that is the case, then we only need to look towards the left of the middle index and we can say

95
00:05:49,050 --> 00:05:51,360
right is equal to middle minus one.

96
00:05:51,900 --> 00:05:56,130
And if this is not the case that means target is greater than array at middle.

97
00:05:56,130 --> 00:05:58,890
And we need to look only towards the right of middle.

98
00:05:58,890 --> 00:06:01,800
So we can say left is equal to middle plus one.

99
00:06:02,010 --> 00:06:04,920
And finally we also have to return minus one over here.

100
00:06:04,920 --> 00:06:08,820
That is the case where we come out of the while loop without returning anything.

101
00:06:08,820 --> 00:06:13,380
So returning minus one means the target value is not there in our array.

102
00:06:13,560 --> 00:06:14,010
All right.

103
00:06:14,040 --> 00:06:16,050
Now let's proceed and complete this part.

104
00:06:16,050 --> 00:06:22,230
So if target is equal to array at middle we have to first check if middle is equal to array dot length

105
00:06:22,230 --> 00:06:25,710
minus one which is the right most index.

106
00:06:25,710 --> 00:06:32,070
If that is the case and target is equal to array at middle right because we are inside this if condition.

107
00:06:32,070 --> 00:06:38,280
So then we have found the right extreme and we can just return middle or array dot length minus one.

108
00:06:38,280 --> 00:06:45,120
So that that means the right most element is the right extreme of the target for that particular target

109
00:06:45,120 --> 00:06:46,770
value and the array given to us.

110
00:06:46,770 --> 00:06:47,400
All right.

111
00:06:47,400 --> 00:06:53,430
So if this is not the case then we are going to check if the next element that is array at middle plus

112
00:06:53,430 --> 00:06:53,910
one.

113
00:06:54,660 --> 00:06:56,190
Is equal to target.

114
00:06:58,520 --> 00:07:04,820
So if the next element is equal to target, then we have to continue looking in the right part to find

115
00:07:04,820 --> 00:07:05,780
the right extreme.

116
00:07:05,780 --> 00:07:09,380
So we're going to say left is equal to middle plus one.

117
00:07:09,380 --> 00:07:15,710
And if this is not the case that is if the next element is not equal to target then we have found the

118
00:07:15,710 --> 00:07:20,720
right extreme and we can just return middle which is the right extreme in that particular case.

119
00:07:20,720 --> 00:07:22,730
So this is how the function works.

120
00:07:22,730 --> 00:07:25,400
Let's now go ahead and test our code.

121
00:07:25,400 --> 00:07:27,080
So we'll call this function.

122
00:07:27,080 --> 00:07:28,790
And let's pass in an array over here.

123
00:07:28,790 --> 00:07:30,200
And the target value.

124
00:07:30,760 --> 00:07:36,100
So let's say the array is one comma, two comma, three comma, three comma, three comma, three comma,

125
00:07:36,100 --> 00:07:37,510
four comma five.

126
00:07:37,510 --> 00:07:39,640
And let's say we are searching for three.

127
00:07:39,700 --> 00:07:42,310
So let's run our code and see what we are getting.

128
00:07:42,310 --> 00:07:44,380
So we are getting two comma five.

129
00:07:44,380 --> 00:07:46,480
So this is index 2012.

130
00:07:46,480 --> 00:07:47,170
That's correct.

131
00:07:47,170 --> 00:07:48,790
And this is three four and five.

132
00:07:48,790 --> 00:07:50,200
So two comma five is correct.

133
00:07:50,200 --> 00:07:52,240
Now what if we were searching for nine.

134
00:07:52,450 --> 00:07:53,590
Let's run the code.

135
00:07:53,590 --> 00:07:56,620
We get minus one comma minus one because nine is not there.

136
00:07:56,620 --> 00:07:57,610
That's also correct.

137
00:07:57,610 --> 00:07:58,990
What if we are searching for one.

138
00:07:58,990 --> 00:08:02,410
Let's try that and we get zero comma zero which is correct.

139
00:08:02,410 --> 00:08:04,000
Which is just this one value over here.

140
00:08:04,000 --> 00:08:04,450
Right.

141
00:08:04,450 --> 00:08:06,190
So our code is working.

142
00:08:06,190 --> 00:08:10,210
Now let's take this sample over here and let's run through the code.

143
00:08:10,210 --> 00:08:14,350
Walk through the code where we are passing this array and the value three.

144
00:08:15,100 --> 00:08:15,490
All right.

145
00:08:15,490 --> 00:08:18,310
We are calling the function search for range iterative.

146
00:08:18,310 --> 00:08:20,350
And this array is passed to it.

147
00:08:20,350 --> 00:08:22,180
So I've just written it down over here.

148
00:08:22,240 --> 00:08:28,450
So we come over here and we are calling the find left extreme function to find the left extreme and

149
00:08:28,450 --> 00:08:31,420
the find right extreme function to find the right extreme.

150
00:08:31,420 --> 00:08:33,430
And then it's just returned as an array.

151
00:08:33,430 --> 00:08:37,360
So let's walk through the find left extreme uh function over here.

152
00:08:37,360 --> 00:08:40,930
So the array is passed to it and the target value is equal to three.

153
00:08:40,960 --> 00:08:42,670
Now left is set to zero.

154
00:08:42,670 --> 00:08:44,320
So left is pointing over here.

155
00:08:44,320 --> 00:08:49,240
And right is point to set to array dot length minus one which is equal to seven.

156
00:08:49,240 --> 00:08:50,770
So right is pointing to seven.

157
00:08:50,770 --> 00:08:54,010
And then we see that left is less than equal to right.

158
00:08:54,010 --> 00:08:55,660
So we're going to calculate middle.

159
00:08:55,660 --> 00:08:58,480
So middle is going to be zero plus seven by two.

160
00:08:58,480 --> 00:08:59,650
And then we are flooring it.

161
00:08:59,650 --> 00:09:01,750
So we are getting middle to be equal to three.

162
00:09:01,750 --> 00:09:04,270
So middle will point at index three.

163
00:09:04,270 --> 00:09:08,140
And then we are seeing that target is equal to array at middle right.

164
00:09:08,140 --> 00:09:10,390
So three over here and three so these are equal.

165
00:09:10,390 --> 00:09:12,820
So we come inside this if condition.

166
00:09:12,820 --> 00:09:14,860
And we are checking if middle is equal to zero.

167
00:09:14,860 --> 00:09:17,050
No that's not the case because middle is three.

168
00:09:17,050 --> 00:09:20,560
And over here we are checking if the previous value is equal to target.

169
00:09:20,560 --> 00:09:24,520
So we see that the previous value is equal to target because this is also three.

170
00:09:24,520 --> 00:09:27,070
So we are setting right to middle minus one.

171
00:09:27,070 --> 00:09:29,980
So right is going to be over here which is index two.

172
00:09:30,310 --> 00:09:30,910
All right.

173
00:09:30,910 --> 00:09:31,990
Again we come over here.

174
00:09:31,990 --> 00:09:34,480
We see that left is still less than equal to right.

175
00:09:35,020 --> 00:09:42,190
So in this iteration we are again calculating middle which is zero plus two by two which is equal to

176
00:09:42,190 --> 00:09:42,460
one.

177
00:09:42,460 --> 00:09:44,470
So middle is going to be equal to one.

178
00:09:44,470 --> 00:09:46,960
So middle is pointing to index one.

179
00:09:46,960 --> 00:09:47,890
At this point.

180
00:09:47,890 --> 00:09:52,660
Now we are checking if target is equal to array at middle right middle is equal to two.

181
00:09:52,660 --> 00:09:53,440
Target is three.

182
00:09:53,440 --> 00:09:54,640
So these are not equal.

183
00:09:54,640 --> 00:09:59,500
So we come over here we check if target is less than array at middle target is the greater value.

184
00:09:59,500 --> 00:10:03,070
So we come over here and we said left is equal to middle plus one.

185
00:10:03,070 --> 00:10:05,260
So left is also going to point over here.

186
00:10:05,260 --> 00:10:07,180
Right is also pointing over here.

187
00:10:07,180 --> 00:10:12,070
So again we come over here we see that left less than equal to right is truthy because they are equal

188
00:10:12,070 --> 00:10:12,820
at this point.

189
00:10:12,820 --> 00:10:17,380
And we calculate middle as left plus right by two which is two itself.

190
00:10:17,380 --> 00:10:19,510
So middle is going to be equal to two.

191
00:10:19,510 --> 00:10:22,840
And we are seeing that target is equal to array at two.

192
00:10:22,840 --> 00:10:23,020
Right.

193
00:10:23,020 --> 00:10:24,400
So this is equal to target.

194
00:10:24,400 --> 00:10:27,550
So we come inside this we check if middle is equal to zero.

195
00:10:27,550 --> 00:10:28,930
No that's not the case.

196
00:10:28,930 --> 00:10:31,510
We check if the previous value is equal to target.

197
00:10:31,510 --> 00:10:34,180
That's not the case because the previous value is two right.

198
00:10:34,180 --> 00:10:39,580
So we come to this else over here and we are just returning middle which is equal to two.

199
00:10:39,610 --> 00:10:43,060
So that's how we find that the left extreme is equal to two.

200
00:10:43,060 --> 00:10:43,360
Right.

201
00:10:43,360 --> 00:10:44,170
So let's see that.

202
00:10:44,170 --> 00:10:46,600
So this function over here returns two.

203
00:10:46,630 --> 00:10:51,850
Therefore over here right when it returns to left extreme is going to be equal to two.

204
00:10:51,850 --> 00:10:54,400
And that's what we are returning in this array over here.

205
00:10:54,400 --> 00:10:55,690
So left extreme is two.

206
00:10:55,720 --> 00:10:58,360
Similarly we will find the right extreme as well.

207
00:10:58,360 --> 00:11:00,550
So let's go ahead and take a look at that as well.

208
00:11:02,210 --> 00:11:04,310
So let me just clear this up a little bit.

209
00:11:06,430 --> 00:11:06,910
All right.

210
00:11:06,910 --> 00:11:09,700
So we are inside the find right extreme function.

211
00:11:09,700 --> 00:11:13,300
And the array and the target value is passed to it.

212
00:11:13,300 --> 00:11:15,250
And again left is set to zero.

213
00:11:15,250 --> 00:11:19,930
And right is set to the right most index which is array dot length minus one.

214
00:11:19,930 --> 00:11:20,650
All right.

215
00:11:20,650 --> 00:11:23,200
And again the target is three itself.

216
00:11:23,200 --> 00:11:26,080
So left is over here and right is over here.

217
00:11:26,080 --> 00:11:28,180
And we come inside the while loop.

218
00:11:28,180 --> 00:11:30,280
And we calculate middle which is equal to three.

219
00:11:30,280 --> 00:11:31,480
So middle is over here.

220
00:11:31,930 --> 00:11:33,730
Now we see that it's equal.

221
00:11:33,730 --> 00:11:39,070
So over here we are checking if middle is the last index is middle equal to array dot length minus one

222
00:11:39,070 --> 00:11:39,700
which is seven.

223
00:11:39,700 --> 00:11:40,840
No that's not true.

224
00:11:40,840 --> 00:11:44,530
So we come over here and we are checking if the next element is equal to target.

225
00:11:44,530 --> 00:11:46,570
Yes the next element is equal to target.

226
00:11:46,570 --> 00:11:49,780
Therefore we are going to set left is equal to middle plus one.

227
00:11:49,780 --> 00:11:51,280
So left is going to be over here.

228
00:11:51,280 --> 00:11:55,420
And then again we come over here we see that left is less than equal to right.

229
00:11:55,420 --> 00:11:57,190
So we calculate the new middle.

230
00:11:57,190 --> 00:12:00,730
So seven plus four is 1111 by two is 5.5.

231
00:12:00,730 --> 00:12:01,660
And we floor it.

232
00:12:01,660 --> 00:12:03,880
So middle is going to be equal to five.

233
00:12:03,880 --> 00:12:06,970
Again we see that target is equal to right middle.

234
00:12:06,970 --> 00:12:08,320
And we come inside.

235
00:12:08,320 --> 00:12:10,780
We see that middle is not the last index.

236
00:12:10,780 --> 00:12:12,790
So this is middle at this point which is five.

237
00:12:12,790 --> 00:12:16,960
And over here we are checking the next element is the next element equal to target.

238
00:12:16,960 --> 00:12:18,040
No that's not true.

239
00:12:18,040 --> 00:12:18,310
Right.

240
00:12:18,310 --> 00:12:22,420
So we come over here and we are going to return middle which is equal to five.

241
00:12:22,420 --> 00:12:24,070
So that's the right extreme.

242
00:12:24,070 --> 00:12:27,760
So that is how we are finding the left extreme and the right extreme.

243
00:12:27,760 --> 00:12:31,030
So we just now we saw that this over here is going to return five.

244
00:12:31,030 --> 00:12:32,890
So that's going to be the right extreme.

245
00:12:32,890 --> 00:12:37,510
And previously we have seen that the left extreme this function over here is going to return two.

246
00:12:37,510 --> 00:12:39,490
And that's going to be the left extreme.

247
00:12:39,490 --> 00:12:41,410
So this is how this function works.

248
00:12:41,410 --> 00:12:44,470
Now let's take a quick look at the space and time complexity.

249
00:12:44,470 --> 00:12:49,900
So the time complexity of this solution is going to be O of two times log n.

250
00:12:49,900 --> 00:12:55,330
Because we are calling one time binary search to find the left extreme and one time binary search to

251
00:12:55,330 --> 00:12:56,410
find the right extreme.

252
00:12:56,410 --> 00:12:59,050
Now this is a constant, so we can just avoid this.

253
00:12:59,050 --> 00:13:04,930
The time complexity is O of log n, and the space complexity is O of one or constant space.

254
00:13:04,930 --> 00:13:10,060
Because we are not using any auxiliary space that can scale with the input scaling.

255
00:13:10,060 --> 00:13:14,440
So the time complexity is O of log n and the space complexity is O of one.