Problem Statement:-

Write an efficient algorithm that searches for a value in an m x n matrix.

This matrix has the following properties:

- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.

**Input** : `matrix = [[1,3,5,7],[10,11,16,20], target = 3,[23,30,34,60]]`

**Result** : `true`

##
__Solution 1__

*this solution is pretty simple,we just traverse the matrix and linearly check the target element, but it will cost n^2 complexity in the worst case.*

**step-1** run two nested loops from `i,j=0`

to `n,m`

.

**step-2** check the `target`

element,

if `matrix[i][j] == target`

, then return `true`

**step-3** if `target`

element not found,return `false`

.

## Java

```
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
for(int i=0; i<matrix.length;i++){
for(int j=0;j<matrix[0].length;j++){
if(matrix[i][j] == target) return true;
}
}
return false;
}
}
```

##
__Solution 2__

*we know that the given matrix is sorted by column-wise & row-wise.so we can solve this problem by applying a binary search algorithm on row-wise and the Time Complexity of this solution will be O(n) + O(logn)*

**step-1** run a loop from `i=0`

to `n`

.

1.get the`ith`

row from the`matrix`

.

`row = matrix[i]`

2.apply binary search algorithm on`row`

,if`target`

element found then return`true`

**step-2** end loop and return `false`

.

## Java

```
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
for(int i=0;i<matrix.length;i++){
int[] row = matrix[i];
int r = Arrays.binarySearch(row,target);
if(r >= 0) return true;
}
return false;
}
}
```

##
__Solution 3__

*treat matrix as a 1D sorted array and apply binary search.*

**step-1** calculate the total elements `n`

of `matrix`

.

**step-2** initialise `low=0`

& `high=n-1`

**step-3** run a loop if `low <= high`

1.find the mid.`mid = low + high`

2.convert 1D array`mid`

index to 2D metrix index.

`row = mid/colSize`

`col = mid%colSize`

3.if`matrix[row][col] == target`

then return`true`

.

4if`target < matrix[row][col]`

then`high = mid-1`

5.if`target > matrix[row][col]`

then`low = mid+1`

**step-4** end loop & return `false`

.

```
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int n = matrix.length;
int m = matrix[0].length;
int low = 0;
int high = ( n*m )- 1;
while(low <= high){
int mid = (low + high) / 2;
int value = matrix[mid/m][mid%m];
if(value == target) return true;
if(value > target)
high = mid-1;
else
low = mid+1;
}
return false;
}
}
```

## Top comments (0)