1
00:00:00,540 --> 00:00:01,560
Welcome back.

2
00:00:01,560 --> 00:00:05,730
Let's now think how we can solve this question in an efficient manner.

3
00:00:05,730 --> 00:00:09,270
Let's say the matrix which is given to us is this one over here.

4
00:00:09,270 --> 00:00:10,860
You can visualize it like this.

5
00:00:10,860 --> 00:00:14,970
So you have four columns and you have three rows right.

6
00:00:14,970 --> 00:00:17,820
So you can see you have three arrays over here inside the array.

7
00:00:17,820 --> 00:00:19,260
So that's why you have three rows.

8
00:00:19,260 --> 00:00:22,380
And then in each array you can see you have four elements.

9
00:00:22,380 --> 00:00:24,030
So that's why you have four columns.

10
00:00:24,030 --> 00:00:26,220
So the values are going to be 1234.

11
00:00:26,250 --> 00:00:31,170
Then you have 5678 and nine 1011 and 12.

12
00:00:31,170 --> 00:00:32,970
So this is the matrix which is given to us.

13
00:00:32,970 --> 00:00:36,030
And let's say the target value is equal to five.

14
00:00:36,030 --> 00:00:42,750
So what would be the brute force method of searching for the value target in the matrix which is given

15
00:00:42,750 --> 00:00:43,170
to us.

16
00:00:43,170 --> 00:00:45,270
So we could just go through each element right.

17
00:00:45,270 --> 00:00:46,440
So we can go check.

18
00:00:46,440 --> 00:00:47,580
Is this equal to five.

19
00:00:47,580 --> 00:00:48,750
Is this equal to five.

20
00:00:48,750 --> 00:00:49,800
Is this equal to five.

21
00:00:49,800 --> 00:00:51,330
Is this equal to five etc..

22
00:00:51,330 --> 00:00:51,600
Right.

23
00:00:51,600 --> 00:00:53,730
So we could just go through each element.

24
00:00:53,730 --> 00:01:01,290
Now if there are m rows and n columns then there are a total of m into n elements over here.

25
00:01:01,290 --> 00:01:01,530
Right.

26
00:01:01,530 --> 00:01:05,970
So you can see that in the worst case we would have to go through each of these elements.

27
00:01:05,970 --> 00:01:08,790
So this method over here is not efficient.

28
00:01:08,790 --> 00:01:09,120
All right.

29
00:01:09,120 --> 00:01:15,480
So if there are m rows and n columns the time complexity of this approach would be o of m into n because

30
00:01:15,480 --> 00:01:17,070
there would be m n elements over here.

31
00:01:17,070 --> 00:01:17,250
Right.

32
00:01:17,250 --> 00:01:20,040
So the time complexity of this would be o of m n.

33
00:01:20,040 --> 00:01:21,750
Now this is not efficient.

34
00:01:21,750 --> 00:01:24,180
Let's see how we can do better than this.

35
00:01:24,210 --> 00:01:24,690
All right.

36
00:01:24,720 --> 00:01:27,420
Now again this let's take another example.

37
00:01:27,420 --> 00:01:30,060
Let's say this is the matrix which is given to us.

38
00:01:30,060 --> 00:01:33,390
So you can see there are five rows and four columns.

39
00:01:33,390 --> 00:01:36,270
And let's say the target is equal to 62.

40
00:01:36,300 --> 00:01:41,550
Now over here the interesting thing is that every array over here is sorted.

41
00:01:41,550 --> 00:01:47,400
And the last element in this array is going to be less than the first element in this array.

42
00:01:47,400 --> 00:01:47,940
Right.

43
00:01:47,940 --> 00:01:54,330
So we are going to make use of this to identify whether the given target is there in the matrix or not

44
00:01:54,330 --> 00:01:55,620
in an efficient manner.

45
00:01:55,620 --> 00:01:57,780
So let's try to think about the approach.

46
00:01:57,780 --> 00:02:01,470
And again remember the clue over here is that we are going to use binary search.

47
00:02:01,470 --> 00:02:04,230
And that's because the data over here is sorted.

48
00:02:04,230 --> 00:02:10,980
Now first we are going to use binary search to find the relevant row in which the target value can be

49
00:02:10,980 --> 00:02:12,450
there, if at all it is there.

50
00:02:12,450 --> 00:02:12,840
All right.

51
00:02:12,840 --> 00:02:14,970
So let's number the rows over here.

52
00:02:14,970 --> 00:02:17,760
So we have 0123 and four.

53
00:02:17,760 --> 00:02:20,970
So these are the indices for each of these five rows.

54
00:02:20,970 --> 00:02:21,450
All right.

55
00:02:21,450 --> 00:02:27,570
So we're going to do binary search to identify if at all which row can have the target value.

56
00:02:27,570 --> 00:02:34,140
Now once we have identified the relevant row then we are going to do binary search on that row to check

57
00:02:34,140 --> 00:02:36,750
if the target value is there in that row or not.

58
00:02:36,750 --> 00:02:42,780
So this is the approach which we will follow to check for the target value in an efficient manner in

59
00:02:42,780 --> 00:02:44,250
the matrix which is given to us.

60
00:02:44,250 --> 00:02:46,650
So let's go ahead and try to walk through this.

61
00:02:46,650 --> 00:02:49,620
So initially we have to identify the relevant row.

62
00:02:49,620 --> 00:02:51,900
So we are going to say top is equal to zero.

63
00:02:52,760 --> 00:02:54,440
And bottom is equal to four.

64
00:02:54,470 --> 00:02:54,740
All right.

65
00:02:54,740 --> 00:02:57,800
So top is equal to zero and bottom is equal to four.

66
00:02:57,800 --> 00:03:00,020
So let's try to do binary search over here.

67
00:03:00,020 --> 00:03:01,460
So we have to find middle.

68
00:03:01,460 --> 00:03:04,580
Middle is going to be zero plus four divided by two.

69
00:03:04,580 --> 00:03:05,870
And then we're going to floor it.

70
00:03:05,870 --> 00:03:07,670
So that's equal to two right.

71
00:03:07,670 --> 00:03:08,990
So middle is equal to two.

72
00:03:08,990 --> 00:03:11,210
So that is this row over here.

73
00:03:11,210 --> 00:03:11,750
All right.

74
00:03:11,750 --> 00:03:19,730
So now we are going to check the least and the greatest value in the row which is the middle row.

75
00:03:19,730 --> 00:03:20,030
All right.

76
00:03:20,030 --> 00:03:22,940
So this row over here the least value is 25.

77
00:03:22,940 --> 00:03:25,010
And the greatest value is 31.

78
00:03:25,010 --> 00:03:31,940
Now if target is less than 25 which is the least value then we have to shift.

79
00:03:31,940 --> 00:03:33,470
Then we have to shift bottom.

80
00:03:33,470 --> 00:03:38,570
And if target is greater than the greatest value which is 31, then we have to shift the top.

81
00:03:38,570 --> 00:03:41,420
So you can see we are doing nothing but binary search over here.

82
00:03:41,420 --> 00:03:48,080
So if target is less than the least value, that means that we can just eliminate this half of the number

83
00:03:48,080 --> 00:03:48,440
of rows.

84
00:03:48,440 --> 00:03:48,740
Right.

85
00:03:48,740 --> 00:03:54,140
And that means we can shift bottom to middle minus one which is this value over here.

86
00:03:54,140 --> 00:03:54,440
Right.

87
00:03:54,440 --> 00:04:00,200
So if target is less than 25 we can say bottom is equal to middle minus one which is eliminating this

88
00:04:00,200 --> 00:04:02,510
half and shifting bottom to this row.

89
00:04:02,510 --> 00:04:02,990
All right.

90
00:04:03,020 --> 00:04:07,070
Now if this is not the case that is if target is greater than 31.

91
00:04:07,070 --> 00:04:07,340
Right.

92
00:04:07,340 --> 00:04:12,650
So that means we can eliminate this part and we can just shift top to this row over here.

93
00:04:12,650 --> 00:04:15,710
That is we can say top is equal to middle plus one.

94
00:04:15,710 --> 00:04:18,410
So you can see again this is nothing but binary search.

95
00:04:18,410 --> 00:04:18,830
All right.

96
00:04:18,830 --> 00:04:20,750
So let's go ahead with this example over here.

97
00:04:20,750 --> 00:04:23,030
Now our target is 62.

98
00:04:23,030 --> 00:04:26,390
And you can see that target is greater than 62.

99
00:04:26,390 --> 00:04:26,690
Right.

100
00:04:26,720 --> 00:04:29,180
Target is not less than 25.

101
00:04:29,180 --> 00:04:30,350
So this is not true.

102
00:04:30,350 --> 00:04:32,210
But target is greater than 31.

103
00:04:32,210 --> 00:04:32,600
All right.

104
00:04:32,600 --> 00:04:36,560
So we are going to set top is equal to middle plus one.

105
00:04:36,560 --> 00:04:40,250
So top is going to be two plus one which is equal to three.

106
00:04:40,700 --> 00:04:41,060
All right.

107
00:04:41,060 --> 00:04:44,360
So we are getting top is equal to three and bottom is equal to four.

108
00:04:44,360 --> 00:04:45,410
We again repeat.

109
00:04:45,410 --> 00:04:48,980
So middle is going to be equal to top plus bottom by two.

110
00:04:48,980 --> 00:04:50,030
And then we are flooring it.

111
00:04:50,030 --> 00:04:51,500
So that's equal to three.

112
00:04:51,500 --> 00:04:51,890
All right.

113
00:04:51,890 --> 00:04:53,540
So that is this row over here.

114
00:04:53,540 --> 00:04:57,350
Again we are going to check whether target is less than 32.

115
00:04:57,380 --> 00:04:57,980
Is that true.

116
00:04:57,980 --> 00:04:59,360
No target is 62 right.

117
00:04:59,360 --> 00:05:01,250
That's not less than the lowest value.

118
00:05:01,250 --> 00:05:03,740
So we don't need to go in this direction.

119
00:05:03,740 --> 00:05:07,040
Now we are checking whether target is greater than 43.

120
00:05:07,040 --> 00:05:07,580
Yes.

121
00:05:07,580 --> 00:05:09,230
Target is greater than 43 right.

122
00:05:09,230 --> 00:05:11,330
62 is greater than 43.

123
00:05:11,330 --> 00:05:11,900
Right.

124
00:05:11,900 --> 00:05:15,500
Therefore we will again shift top to middle plus one.

125
00:05:15,500 --> 00:05:19,520
So top is going to be equal to middle which is three plus one which is four.

126
00:05:19,520 --> 00:05:21,200
So we have eliminated this part.

127
00:05:21,200 --> 00:05:21,620
All right.

128
00:05:21,620 --> 00:05:23,720
So top is four and bottom is four.

129
00:05:23,720 --> 00:05:28,070
So again we continue middle is going to be equal to top plus bottom by four.

130
00:05:28,070 --> 00:05:28,970
And then we floor it.

131
00:05:28,970 --> 00:05:32,300
So we get middle is four plus four by two which is equal to four.

132
00:05:32,300 --> 00:05:32,750
All right.

133
00:05:32,750 --> 00:05:36,800
Now in this row we have the lowest value which is 45.

134
00:05:36,800 --> 00:05:39,380
And the largest value which is 65.

135
00:05:39,380 --> 00:05:39,770
All right.

136
00:05:39,770 --> 00:05:44,690
So again we proceed now is middle less than 45.

137
00:05:44,720 --> 00:05:45,290
No.

138
00:05:45,290 --> 00:05:45,590
Right.

139
00:05:45,590 --> 00:05:46,700
So that's not true.

140
00:05:46,700 --> 00:05:49,160
So middle the the target not the middle value.

141
00:05:49,160 --> 00:05:51,350
The target is target less than 45.

142
00:05:51,350 --> 00:05:52,040
No.

143
00:05:52,040 --> 00:05:53,960
Is target greater than 65.

144
00:05:53,960 --> 00:05:54,350
No.

145
00:05:54,350 --> 00:05:54,680
Right.

146
00:05:54,680 --> 00:06:02,990
So because target which is 62 is not less than the lowest value and not greater than the largest value,

147
00:06:03,020 --> 00:06:07,970
we have found the row in which target can exist, if at all it exists.

148
00:06:07,970 --> 00:06:09,800
Again, remember it's not necessary.

149
00:06:09,800 --> 00:06:13,130
If target was 61, then you can see it's not over here.

150
00:06:13,130 --> 00:06:17,000
But even in that case also we would have still identified the same row.

151
00:06:17,000 --> 00:06:17,360
All right.

152
00:06:17,360 --> 00:06:22,340
So we have identified the row in which the target value can be there, if at all.

153
00:06:22,340 --> 00:06:24,770
It is there in the matrix which is given to us.

154
00:06:24,770 --> 00:06:25,250
All right.

155
00:06:25,250 --> 00:06:26,270
So let's proceed.

156
00:06:26,950 --> 00:06:33,130
So, having identified that only this row is relevant, to check for the presence of the target value,

157
00:06:33,160 --> 00:06:38,950
we are going to run binary search on this particular row over here, which is nothing but normal binary

158
00:06:38,950 --> 00:06:41,410
search, which we have already previously discussed.

159
00:06:41,410 --> 00:06:43,180
So let's go ahead and do that over here.

160
00:06:43,180 --> 00:06:46,750
So the indices over here are 012 and three.

161
00:06:46,750 --> 00:06:48,850
Now we are going to have a left pointer.

162
00:06:48,850 --> 00:06:50,500
So left is going to be equal to zero.

163
00:06:50,500 --> 00:06:52,630
And right is equal to three.

164
00:06:52,630 --> 00:06:53,290
All right.

165
00:06:53,320 --> 00:06:56,890
Now we are going to find the middle which is left plus right divided by two.

166
00:06:56,890 --> 00:06:57,970
And then we are flooring it.

167
00:06:57,970 --> 00:07:01,030
So zero plus three divided by two gives us 1.5.

168
00:07:01,030 --> 00:07:03,910
And when we floor it we get middle is equal to one.

169
00:07:03,910 --> 00:07:06,250
So that's pointing to this index over here.

170
00:07:06,250 --> 00:07:06,640
All right.

171
00:07:06,640 --> 00:07:09,850
So at index one the value is equal to 60.

172
00:07:09,850 --> 00:07:12,640
Now 60 is not equal to the target value.

173
00:07:12,640 --> 00:07:13,030
All right.

174
00:07:13,030 --> 00:07:19,420
So we also see that 62 the target value is greater than the value at the index middle right which is

175
00:07:19,420 --> 00:07:19,900
60.

176
00:07:19,900 --> 00:07:22,360
So therefore we are going to shift left.

177
00:07:22,360 --> 00:07:26,110
So we are going to shift left to middle plus one which is two.

178
00:07:26,110 --> 00:07:28,780
So left is going to change from 0 to 2.

179
00:07:28,810 --> 00:07:31,210
So left is two and right is at three.

180
00:07:31,210 --> 00:07:34,810
Again we calculate the new middle which is two plus three divided by two.

181
00:07:34,810 --> 00:07:36,040
And then we are flooring it.

182
00:07:36,040 --> 00:07:37,990
So that's 2.5.

183
00:07:37,990 --> 00:07:39,730
And then when we floor it we get two.

184
00:07:39,760 --> 00:07:43,030
So middle is going to be equal to two which is this index over here.

185
00:07:43,030 --> 00:07:47,350
And we can see that the target is equal to the value at the middle index.

186
00:07:47,350 --> 00:07:49,450
And hence we have found the target.

187
00:07:49,450 --> 00:07:51,430
And we can just return true.

188
00:07:51,430 --> 00:07:55,120
So this is how we are going to solve this question in an efficient manner.

189
00:07:55,120 --> 00:08:01,000
You can see that instead of doing m and m into n operations, which was the brute force approach over

190
00:08:01,000 --> 00:08:04,840
here, we have to do only log m plus log N operations.

191
00:08:04,840 --> 00:08:05,140
Right.

192
00:08:05,140 --> 00:08:07,840
So that will be the time complexity of this solution.

193
00:08:07,840 --> 00:08:08,260
Right.

194
00:08:08,260 --> 00:08:15,250
So the time complexity, if there are m rows and n columns is equal to log m plus log n.

195
00:08:15,250 --> 00:08:16,600
Now why log m.

196
00:08:16,600 --> 00:08:18,130
That's to find the row right.

197
00:08:18,130 --> 00:08:24,520
So to find the correct row we did a binary search with m elements which is the number of rows.

198
00:08:24,520 --> 00:08:26,410
That's why we have log m over here.

199
00:08:26,410 --> 00:08:30,850
And then we have log n over here which is done on that particular array.

200
00:08:30,850 --> 00:08:31,330
Right.

201
00:08:31,330 --> 00:08:32,470
Or the particular row.

202
00:08:32,470 --> 00:08:36,760
So the array over here is having n elements which is the number of columns.

203
00:08:36,760 --> 00:08:42,130
So that's why we have log n operations to do binary search on that particular row.

204
00:08:42,130 --> 00:08:46,360
And log m plus log n is nothing but log m into n.

205
00:08:46,360 --> 00:08:49,780
So the time complexity over here is o of log m n.

206
00:08:49,780 --> 00:08:51,760
And what about the space complexity?

207
00:08:51,760 --> 00:08:58,120
As we have implemented this iteratively, and as we are not using any auxiliary space, the space complexity

208
00:08:58,120 --> 00:09:01,150
of this solution is O of one or constant space.