New update is available. Click here to update.

Last Updated: 14 Dec, 2020

Difficulty: Easy

```
Given Matrix : 1 1 and Target : 8
4 8
The output should be "TRUE" as 8 is present in the Matrix.
```

```
The first line of input contains an integer 'T' representing the number of test cases Then the test case follows :
The first line of each test case contains three space-separated integers 'M', 'N' and 'TARGET' where 'M' and 'N' denote the number of rows and columns of the 'MAT', respectively and 'TARGET' is the integer to be found.
From the second line of each test case, the next 'N' lines represent the rows of the 'MAT'. Every row contains 'M' single space-separated integers.
```

```
For each test case, print “TRUE” if 'TARGET' is present in the 'MAT', else print “FALSE”.
```

```
You do not need to print anything, it has already been taken care of. Just implement the function.
```

```
1 <= T <= 10^2
1 <= N <= 50
1 <= M <= 50
-10^5 <= MAT[i], TARGET <= 10^5
Time Limit : 1 sec
```

```
Can you solve this problem in less than O(M*N) time complexity ?
```

```
1
3 4 8
1 2 3 4
5 6 7 8
9 10 11 12
```

```
TRUE
```

```
The 'TARGET' = 8 exists in the 'MAT' at index (1, 3).
```

```
2
3 3 78
1 2 4
6 7 8
9 10 34
2 2 8
1 1
4 8
```

```
FALSE
TRUE
```

```
The 'TARGET' = 78 do not exists in the 'MAT'.
The 'TARGET' = 8 exists in the 'MAT' at index (1, 1).
```

Since every row of the given matrix is sorted and the first element of row ‘i’ is greater than the last element of row ‘i-1’ (if exist), all the M*N elements of the matrix are arranged in an ascending order.

The intuition behind this approach is that since we can map indices of a matrix to an array, we can treat the given matrix as an array/list of M*N sorted integers.

We map the indices of matrix elements to a 1D array as follows :

- If we copy the elements of a matrix (say ‘MAT’) to an array (say ‘ARR’) in a row-wise manner, then the element ‘MAT[i][j]' is equal to ‘ARR[N*i+j]’, where ‘N’ denotes the number of columns in ‘MAT’.
- Similarly, converting ‘ARR’ back to ‘MAT’, the element ‘ARR[i]’ is equal to ‘MAT[i/N][i%N]’ as ‘ARR’ contains M*N elements, so ‘rowNum’ is equal to i/N and ‘colNum' is equal to i%N.

Now, we simply use binary search to find the ‘TARGET’.

SIMILAR PROBLEMS

Find The Single Element

Posted: 30 Oct, 2022

Difficulty: Easy

Find minimum

Posted: 8 Nov, 2022

Difficulty: Hard

Search In A Sorted 2D Matrix

Posted: 23 Nov, 2022

Difficulty: Moderate

Spiral Matrix

Posted: 24 Nov, 2022

Difficulty: Easy

Fake Coin Problem

Posted: 24 Dec, 2022

Difficulty: Easy

Popular Interview Problems: