1
00:00:00,650 --> 00:00:01,580
Hi everyone.

2
00:00:01,580 --> 00:00:03,650
Let's do this question right.

3
00:00:03,650 --> 00:00:11,180
An efficient algorithm that searches for a value target in an m into n integer matrix.

4
00:00:11,180 --> 00:00:13,760
This matrix has the following properties.

5
00:00:13,910 --> 00:00:16,940
Integers in each row are sorted from left to right.

6
00:00:16,940 --> 00:00:22,070
The first integer of each row is greater than the last integer in the previous of the previous row.

7
00:00:22,070 --> 00:00:25,730
If the value is there in the matrix, return true, else false.

8
00:00:25,730 --> 00:00:28,430
Now first let's think about what is a matrix.

9
00:00:28,430 --> 00:00:31,280
Now a matrix is nothing but a 2D array.

10
00:00:31,280 --> 00:00:34,130
So that's just an array where each element is an array.

11
00:00:34,130 --> 00:00:35,540
So let's take an example.

12
00:00:35,540 --> 00:00:38,240
Let's say this is the matrix which is given to us.

13
00:00:38,240 --> 00:00:41,660
So you can see that this is nothing but an array with three elements.

14
00:00:41,660 --> 00:00:43,970
And each element is an array itself.

15
00:00:43,970 --> 00:00:46,250
Now we can visualize this like this also.

16
00:00:46,250 --> 00:00:48,800
So typically a matrix is drawn out like this.

17
00:00:49,880 --> 00:00:54,080
Now the values in this array one, two, three are these three values over here.

18
00:00:54,080 --> 00:00:56,180
And then we have four five, six over here.

19
00:00:56,870 --> 00:00:59,210
And we have 789 over here.

20
00:00:59,210 --> 00:01:01,370
So this is a matrix which is given to us.

21
00:01:01,370 --> 00:01:04,460
Now in this matrix we have to search for a value.

22
00:01:04,460 --> 00:01:07,310
Let's say target is given as five.

23
00:01:07,310 --> 00:01:09,500
Now because five is there in this matrix.

24
00:01:09,500 --> 00:01:10,850
We have to return true.

25
00:01:10,850 --> 00:01:15,440
If the target value, let's say was ten, then we would have to return false because it's not there

26
00:01:15,440 --> 00:01:16,940
in the matrix which is given to us.

27
00:01:16,940 --> 00:01:18,260
So this is the question.

28
00:01:18,260 --> 00:01:21,500
And then remember we are asked to write an efficient algorithm.

29
00:01:21,500 --> 00:01:21,860
All right.

30
00:01:21,860 --> 00:01:23,870
So that's the catch over here.

31
00:01:23,870 --> 00:01:27,740
And then also let's take a look at the properties which is given.

32
00:01:27,740 --> 00:01:32,420
It's mentioned over here that integers in each row are sorted from left to right.

33
00:01:32,420 --> 00:01:34,880
So from left to right the integers are sorted.

34
00:01:34,880 --> 00:01:40,460
And then it's mentioned that the first integer of each row is greater than the last integer of the previous

35
00:01:40,460 --> 00:01:40,730
row.

36
00:01:40,730 --> 00:01:42,200
So over here you have three.

37
00:01:42,200 --> 00:01:44,420
This would be greater than three, which is four.

38
00:01:44,420 --> 00:01:47,810
And if this is six, whatever comes over here has to be greater than six.

39
00:01:47,810 --> 00:01:50,360
It can be seven or 70 or 17 whatever.

40
00:01:50,360 --> 00:01:51,920
But it has to be greater than six.

41
00:01:51,920 --> 00:01:53,840
So that is what is mentioned in the question.

42
00:01:53,840 --> 00:01:58,460
So let's go ahead and write a few test cases to think about this question.

43
00:01:58,460 --> 00:02:00,050
We have already seen one test case.

44
00:02:00,050 --> 00:02:05,660
If this is the matrix which is given to us, and if the target is equal to five, then we have to return

45
00:02:05,660 --> 00:02:09,050
true because the value five is there in the given matrix.

46
00:02:09,050 --> 00:02:13,790
Now, if the target was equal to ten, then we would have to return false again.

47
00:02:13,790 --> 00:02:16,160
If the matrix is empty right?

48
00:02:16,160 --> 00:02:22,310
Then if there is a target, for example something like one, then we have to return false because we

49
00:02:22,310 --> 00:02:24,230
can see that the matrix is empty.

50
00:02:24,230 --> 00:02:27,380
Therefore, one is not present in the matrix which is given to us.

51
00:02:27,380 --> 00:02:29,030
So we have understood the question.

52
00:02:29,030 --> 00:02:34,250
And remember over here you can see that it's mentioned that the data is sorted.

53
00:02:34,250 --> 00:02:36,710
And we are asked to write an efficient algorithm.

54
00:02:36,710 --> 00:02:37,700
So these are hints.

55
00:02:37,700 --> 00:02:42,650
So we know that whenever the data is sorted we can make use of the binary search algorithm.

56
00:02:42,650 --> 00:02:47,840
So try to think how you can make use of the binary search algorithm to write an efficient solution to

57
00:02:47,840 --> 00:02:48,500
this question.