1
00:00:01,750 --> 00:00:02,410
Hi, everyone.

2
00:00:02,440 --> 00:00:06,100
So today we are going to discuss this question so rich in Matrix.

3
00:00:07,220 --> 00:00:16,460
OK, so input will basically be a matrix and our target value that we have to search inside the Matrix.

4
00:00:16,820 --> 00:00:21,200
OK, but this matrix is not a normal matrix.

5
00:00:21,260 --> 00:00:24,290
OK, so this is not a normal matrix.

6
00:00:25,010 --> 00:00:27,720
The Matrix has a property which is the property.

7
00:00:27,980 --> 00:00:31,490
So this matrix, each rule is sorted.

8
00:00:33,450 --> 00:00:35,670
And each column is sorted.

9
00:00:35,820 --> 00:00:40,940
OK, so you can see so this is sorted two, six, seven, 11.

10
00:00:41,010 --> 00:00:43,680
This is a sorted row, three, eight, 10, 12.

11
00:00:43,770 --> 00:00:46,830
This is a sorted row for nine, 11, 13.

12
00:00:46,860 --> 00:00:49,400
This is a sorted five, 15, 16 and 18.

13
00:00:49,460 --> 00:00:52,910
OK, so in this matrix, each are always sorted in descending order.

14
00:00:53,070 --> 00:00:55,690
And similarly, each column is a sorted.

15
00:00:55,740 --> 00:00:59,340
OK, so this is two, then three, then four and then five.

16
00:00:59,550 --> 00:01:04,560
Similarly, six, eight, nine, 15, seven, 10, 11 and 16.

17
00:01:04,560 --> 00:01:07,450
Sorted 11, 12, 13 and 18.

18
00:01:07,500 --> 00:01:14,340
OK, so each row and column in the government is basically sorted and the question is basically given

19
00:01:14,340 --> 00:01:15,220
our target value.

20
00:01:15,240 --> 00:01:17,090
So in this case, the target values nine.

21
00:01:17,130 --> 00:01:20,200
So given a target value, we have to return, true or false.

22
00:01:20,400 --> 00:01:22,490
So we will we have to return double in value.

23
00:01:22,950 --> 00:01:28,350
So this value will be true if the given target is present inside the Matrix, and this will default

24
00:01:28,350 --> 00:01:31,380
if the given target value is not present inside The Matrix.

25
00:01:31,440 --> 00:01:35,450
OK, so this question is basically present on later.

26
00:01:35,520 --> 00:01:37,470
OK, so you can see here.

27
00:01:37,500 --> 00:01:40,890
OK, so each rule is sorted and each column is sorted.

28
00:01:41,790 --> 00:01:44,000
OK, so how we can solve this question.

29
00:01:44,400 --> 00:01:48,140
So the first one ways to solve this question, let us discuss the approaches.

30
00:01:48,390 --> 00:01:51,180
So the first approach is the brute force approach.

31
00:01:51,210 --> 00:01:56,790
OK, so what this approach will say is just iterate over all the metrics, just outraged over the Matrix,

32
00:01:56,940 --> 00:02:00,930
basically go through all the elements, if you will, find the target value, don't draw.

33
00:02:00,950 --> 00:02:01,980
Otherwise it involves.

34
00:02:02,010 --> 00:02:05,310
OK, so we will go through each and every element.

35
00:02:06,060 --> 00:02:07,820
So what will be the time complexity.

36
00:02:08,340 --> 00:02:14,880
So let's say the dimensions of the Matrix are I'm in Darwin, so the time complexity will be Emman and

37
00:02:14,880 --> 00:02:16,900
the space complexity will be alderwoman.

38
00:02:16,980 --> 00:02:22,410
OK, so this brute forces go through each and every element in the matrix and compared that element

39
00:02:22,410 --> 00:02:23,550
with the target value.

40
00:02:23,940 --> 00:02:26,790
OK, if you found a target value redrado as it unfolds.

41
00:02:27,180 --> 00:02:33,420
So this is the time when this space complexity, the second approach is basically binary search, binary

42
00:02:33,420 --> 00:02:34,380
search each arrow.

43
00:02:34,920 --> 00:02:39,180
OK, so we can see each arrow is a sorted row.

44
00:02:39,450 --> 00:02:44,790
So we will go through the first rule, we will apply the binary search, come to the second rule, apply

45
00:02:44,800 --> 00:02:49,890
the binary search, come to the third row applied by the result, come today for true applied binary

46
00:02:49,890 --> 00:02:50,250
search.

47
00:02:50,490 --> 00:02:56,190
So we are iterating over the rules so that time complexity will be so since we are dating over the rules.

48
00:02:56,190 --> 00:03:00,300
So we have Amaru's and for searching what we are doing.

49
00:03:00,300 --> 00:03:03,230
So this is basically in columns, therefore searching.

50
00:03:03,270 --> 00:03:04,560
We are using binary search.

51
00:03:05,250 --> 00:03:10,620
So it will be emond to login and to login because we are using binary search.

52
00:03:10,660 --> 00:03:15,190
OK, so we are optimizing our time, complexity and virtual space complexity.

53
00:03:15,210 --> 00:03:17,690
So still, this is our Ardavan.

54
00:03:18,270 --> 00:03:20,620
OK, now let's discuss the best approach.

55
00:03:21,210 --> 00:03:24,510
So this is this method is called staircase search.

56
00:03:25,490 --> 00:03:28,480
OK, this is called staircase search.

57
00:03:29,070 --> 00:03:36,240
Now, what this method says is basically you move at the move, at this element, basically the opposite

58
00:03:36,240 --> 00:03:36,630
element.

59
00:03:36,660 --> 00:03:39,240
OK, so move to the top right element.

60
00:03:43,380 --> 00:03:44,370
Move to the top, right?

61
00:03:44,670 --> 00:03:49,950
So this is 11 now, compared 11 with nine, so 11 is bigger than move left.

62
00:03:51,780 --> 00:03:55,500
OK, compare seven with nine, so this is a smaller move down.

63
00:03:57,220 --> 00:04:01,060
Now, compare ten with nine, so ten is bigger than move left.

64
00:04:02,400 --> 00:04:09,750
Now, compare it with nine so it is smaller, move down now, compare nine with nine to return.

65
00:04:09,750 --> 00:04:10,030
True.

66
00:04:10,310 --> 00:04:15,000
OK, so it says move their top rate element now compared the element.

67
00:04:16,260 --> 00:04:20,560
With the target value, so if that element is greater than the target value, what we will do.

68
00:04:20,579 --> 00:04:22,620
So basically you will move left.

69
00:04:22,650 --> 00:04:25,620
So for moving left, we will do column minus minus.

70
00:04:26,340 --> 00:04:26,770
OK.

71
00:04:26,970 --> 00:04:32,190
And if the element is smaller, then the target value we have to move down.

72
00:04:32,400 --> 00:04:36,360
OK, so for moving down, I will do rule plus plus.

73
00:04:36,940 --> 00:04:40,350
OK, so this is 11 11 element.

74
00:04:40,350 --> 00:04:45,390
So the element is greater than the target value then where the nine will obviously nine will lie in

75
00:04:45,390 --> 00:04:50,230
the left hand side because the left hand side of the 11, the elements are smaller.

76
00:04:50,250 --> 00:04:55,740
We cannot move down because if we will move down then all the elements will be greater than 11 and we

77
00:04:55,740 --> 00:04:56,760
have to find nine.

78
00:04:57,090 --> 00:05:01,560
OK, so nine element can only be present in the left hand side of the 11.

79
00:05:02,550 --> 00:05:08,810
Now, compare seven with the nine, so seven element is smaller than nine, if you will move left,

80
00:05:08,820 --> 00:05:14,000
then you will get smaller element, then seven, OK, because that rule is sorted.

81
00:05:14,220 --> 00:05:15,970
So we cannot move left.

82
00:05:15,990 --> 00:05:20,040
We can only move down now, compared then with the nine.

83
00:05:20,160 --> 00:05:21,300
So 10 is bigger.

84
00:05:21,480 --> 00:05:24,330
If you will move down, you will get bigger element then.

85
00:05:24,330 --> 00:05:25,870
Then but we have to find nine.

86
00:05:26,040 --> 00:05:30,810
So the only option is to move left and it is smaller than nine.

87
00:05:30,960 --> 00:05:32,580
So obviously you cannot move left.

88
00:05:32,580 --> 00:05:35,480
If you will move left, you cannot you can never find nine.

89
00:05:35,760 --> 00:05:37,890
So the only option is to move down.

90
00:05:38,340 --> 00:05:44,640
OK, so this staircase approach, this staircase approach is basically making the use of the property

91
00:05:44,640 --> 00:05:46,740
of the Matrix Room and Colombo times.

92
00:05:47,280 --> 00:05:50,880
OK, and now why it is called staircase approach because you can see.

93
00:05:51,150 --> 00:05:53,730
So this resembles the staircase.

94
00:05:53,760 --> 00:05:57,330
OK, so this shape, the way in we are searching.

95
00:05:57,540 --> 00:05:58,290
This is nothing.

96
00:05:58,290 --> 00:05:59,640
This is just a staircase.

97
00:05:59,850 --> 00:06:01,950
So that's why it is called a staircase approach.

98
00:06:02,460 --> 00:06:04,170
OK, and the logic is very simple.

99
00:06:04,170 --> 00:06:08,280
If the current element is greater than the target value, then obviously you have to move left.

100
00:06:08,310 --> 00:06:11,010
If you want to find out the target, well, you cannot move down.

101
00:06:11,280 --> 00:06:13,780
So moving left, I am doing minus minus.

102
00:06:14,610 --> 00:06:15,750
And this is the case.

103
00:06:15,960 --> 00:06:22,340
Obviously, the only thing, the only way to find out the target value if we will move down so far moving

104
00:06:22,350 --> 00:06:28,300
down I'm being replaced is very simple now over the time and the space complexity for using this approach.

105
00:06:28,350 --> 00:06:29,820
So space complexity is nothing.

106
00:06:30,510 --> 00:06:34,650
This will be a drama and complex complexity is basically in the worst case, what will happen.

107
00:06:34,920 --> 00:06:37,890
So I will go through this and then I will go through this.

108
00:06:38,250 --> 00:06:42,870
So in the worst case, complexity will be emplacing when the element is not present.

109
00:06:43,510 --> 00:06:45,630
OK, so you can see.

110
00:06:46,800 --> 00:06:48,750
First, our time complexity was immense.

111
00:06:48,870 --> 00:06:51,030
Now it is linear emplacing.

112
00:06:51,720 --> 00:06:54,590
OK, so this is also an example.

113
00:06:54,600 --> 00:07:00,040
Let us use this approach in this example so we have to find the target value five.

114
00:07:00,510 --> 00:07:02,850
OK, so let me draw here.

115
00:07:02,850 --> 00:07:12,600
So I have one for seven, 11, 15, then to three, then 18, five, six, 13 and 21, eight, nine,

116
00:07:12,600 --> 00:07:20,550
14, 23, well, 16, 17, 26, 19, 22, 24 and 30.

117
00:07:20,770 --> 00:07:23,320
OK, so the target value is basically five.

118
00:07:23,820 --> 00:07:29,980
So according to staircase approach, come here at the top right now, compare 15 with three.

119
00:07:30,780 --> 00:07:32,350
So obviously 15 is bigger.

120
00:07:32,370 --> 00:07:34,860
So the only way to find five is to move left.

121
00:07:35,400 --> 00:07:37,110
Again, 11 is bigger than five.

122
00:07:37,380 --> 00:07:41,430
So only way is to find five is basically move left again.

123
00:07:41,730 --> 00:07:43,340
Seven is greater than five.

124
00:07:43,770 --> 00:07:45,800
So five can lie on the left hand side.

125
00:07:45,810 --> 00:07:46,920
So move to the left.

126
00:07:47,400 --> 00:07:48,930
Now compare four with five.

127
00:07:49,470 --> 00:07:53,100
Obviously, the fifth element can represent downside only.

128
00:07:53,760 --> 00:07:54,620
So move down.

129
00:07:55,080 --> 00:07:57,080
And now we will get our element five.

130
00:07:57,090 --> 00:07:58,230
So we will return to.

131
00:07:59,840 --> 00:08:06,040
OK, now let's find out the settlement, which is 20, OK, so I am standing here 15.

132
00:08:06,590 --> 00:08:12,230
So if you want to find 20, you will move down because if you will move down, you will get all the

133
00:08:12,230 --> 00:08:13,700
elements which are good than 15.

134
00:08:14,060 --> 00:08:14,800
So move down.

135
00:08:15,200 --> 00:08:18,290
So 19, obviously, if you want to find out, 20, move down.

136
00:08:18,290 --> 00:08:20,570
So I will move down now.

137
00:08:20,570 --> 00:08:21,460
22 is bigger.

138
00:08:21,470 --> 00:08:22,400
So move left.

139
00:08:22,880 --> 00:08:23,960
16 is smaller.

140
00:08:23,960 --> 00:08:24,740
So move down.

141
00:08:25,370 --> 00:08:26,590
17 is smaller.

142
00:08:26,600 --> 00:08:27,230
Move down.

143
00:08:28,070 --> 00:08:31,240
This bigger move left 23 is a bigger move left.

144
00:08:31,680 --> 00:08:34,010
21 is bigger than 20 moved left.

145
00:08:34,370 --> 00:08:36,299
18 is smaller than 20 moved down.

146
00:08:36,890 --> 00:08:41,210
OK, so if you will move down, I want my tax will finish and we will stop.

147
00:08:41,659 --> 00:08:43,250
And what we will do, we will return.

148
00:08:43,250 --> 00:08:43,730
False.

149
00:08:44,450 --> 00:08:47,450
OK, so you can see this is a staircase approach.

150
00:08:47,480 --> 00:08:50,180
This resembles the shape of a staircase.

151
00:08:50,210 --> 00:08:54,590
OK, so that's where this method of searching is called staircase.

152
00:08:56,320 --> 00:09:00,940
OK, so now, since you have understood the logic, I think chording will not be a problem.

153
00:09:00,970 --> 00:09:03,360
OK, so now let us write the code.

154
00:09:04,320 --> 00:09:11,640
OK, so the court will be very, very simple, so now let us find out the rules and the columns.

155
00:09:11,670 --> 00:09:12,000
OK.

156
00:09:14,240 --> 00:09:16,490
So it is basically how many rules are there?

157
00:09:20,280 --> 00:09:22,530
So this is matrix size.

158
00:09:26,140 --> 00:09:27,940
And now let's find out the columns.

159
00:09:29,290 --> 00:09:32,070
So this is nothing but mattocks of zero dollars.

160
00:09:36,570 --> 00:09:45,120
OK, so let us handle first case, so if the target value is basically smaller than.

161
00:09:48,050 --> 00:09:49,940
The smallest value in the Matrix.

162
00:09:49,970 --> 00:09:51,500
OK, so you can see.

163
00:09:52,980 --> 00:09:56,240
This is basically the smallest element in the Matrix.

164
00:09:56,300 --> 00:10:01,440
OK, this will be the smallest element of the Murdochs because it will move right or you will move down,

165
00:10:01,440 --> 00:10:02,430
the elements will increase.

166
00:10:02,670 --> 00:10:05,290
And similarly, this is the largest element.

167
00:10:05,310 --> 00:10:09,900
So this is the largest element of this matrix and this is the smallest element.

168
00:10:09,930 --> 00:10:10,350
OK.

169
00:10:12,640 --> 00:10:21,430
So basically, if the target value is smaller, then the smallest element of the matrix or the target

170
00:10:21,640 --> 00:10:28,480
value is basically bigger than the biggest, the largest element in the matrix.

171
00:10:29,290 --> 00:10:31,540
So this is basically euros minus one.

172
00:10:35,030 --> 00:10:36,350
And Collins, minus one.

173
00:10:39,260 --> 00:10:44,660
So if the target value is greater than the largest value, then obviously you can directly return false

174
00:10:44,660 --> 00:10:46,700
because the element will not be present.

175
00:10:46,760 --> 00:10:50,890
OK, OK, so now let us trade over the metrics.

176
00:10:50,900 --> 00:10:52,310
OK, so.

177
00:10:55,270 --> 00:10:57,460
Let us take two variables, so.

178
00:10:58,550 --> 00:11:05,540
I the satellite letter, Tawadros and I have a very bulgy, so this will add it over the columns, so

179
00:11:05,540 --> 00:11:09,980
this is nothing but so I have to move to the last column.

180
00:11:09,980 --> 00:11:11,780
So this is columns minus one.

181
00:11:13,420 --> 00:11:16,480
OK, so what the condition?

182
00:11:17,550 --> 00:11:23,610
So while Daryl Savelli is less than construes minus one.

183
00:11:25,840 --> 00:11:26,380
And.

184
00:11:28,330 --> 00:11:31,520
While is basically greater than or equal to zero.

185
00:11:32,260 --> 00:11:36,270
OK, so what I have to do compared the current element.

186
00:11:36,550 --> 00:11:39,590
So this is basically I am moving to the top right corner.

187
00:11:39,610 --> 00:11:42,580
OK, so move to the top.

188
00:11:42,580 --> 00:11:42,910
Right.

189
00:11:44,880 --> 00:11:50,510
And since I have to do so, I will do plus plus I, I will look on a minus minus.

190
00:11:50,520 --> 00:11:53,700
So that's why this condition, because I will luchador plus plus.

191
00:11:53,700 --> 00:11:56,910
And that's why this condition because I would look whams minus minus.

192
00:11:57,360 --> 00:11:59,580
OK, so if the current element.

193
00:12:00,630 --> 00:12:01,260
Which is.

194
00:12:02,750 --> 00:12:03,950
Networks of AIG.

195
00:12:05,460 --> 00:12:11,550
So there are three cases, first cases very simple, we found out the target element, so in this case,

196
00:12:11,670 --> 00:12:12,450
I can return.

197
00:12:12,450 --> 00:12:12,750
True.

198
00:12:12,820 --> 00:12:14,880
OK, you can see the return type Izabel.

199
00:12:15,150 --> 00:12:16,950
So I have to return either true or false.

200
00:12:17,340 --> 00:12:21,360
So if you have found the element, the target element we can return to.

201
00:12:22,110 --> 00:12:23,520
Now, there are two more cases.

202
00:12:26,510 --> 00:12:27,710
The second case can be.

203
00:12:32,480 --> 00:12:36,980
If the current element is smaller than the target value.

204
00:12:38,240 --> 00:12:42,790
Then would I have to do I have to move down so far, moving down, I have to rob placeless.

205
00:12:43,280 --> 00:12:47,300
OK, so the name of the variable is basically I so I will do a placeless.

206
00:12:50,660 --> 00:12:52,220
And in the terrorist case.

207
00:12:55,240 --> 00:13:02,530
So if the current element is getting their target value, then we'd have to do so, I have to move left.

208
00:13:02,590 --> 00:13:05,400
So for moving left, I have to do a column minus minus.

209
00:13:06,310 --> 00:13:13,750
So here the variable column is basically variable G, OK, and if I reach the end of the loop, I can

210
00:13:13,750 --> 00:13:14,690
return false.

211
00:13:14,710 --> 00:13:16,660
Basically the target value is not present.

212
00:13:16,690 --> 00:13:17,020
OK.

213
00:13:20,200 --> 00:13:22,000
OK, so now let us submit our good.

214
00:13:26,660 --> 00:13:30,200
OK, so if our taxes and we are getting a random error.

215
00:13:30,450 --> 00:13:33,980
OK, so what I have to do, I have to handle the situation here.

216
00:13:36,070 --> 00:13:40,680
So if basically Rose is zero, if there are not any rules, what can I do?

217
00:13:41,350 --> 00:13:42,460
I can return false.

218
00:13:49,540 --> 00:13:53,230
So, again, if the columns are zero, then I can also read Danville's.

219
00:14:06,140 --> 00:14:11,960
OK, so our goal is working, so as we discussed the time and the space complexity for using this takes,

220
00:14:11,990 --> 00:14:16,000
approaches, spaces or driven and time is Ampligen.

221
00:14:16,130 --> 00:14:16,460
OK.

222
00:14:17,620 --> 00:14:19,690
So if you're an out, you can ask me, OK, thank you.