Striver's SDE Sheet Journey - #13 Search in a 2d Matrix
Tags: programming, beginners, java, computerscience
Published: 2022-01-13 12:33:02

> **<u>Problem Statement</u> :-**

Write an efficient algorithm that searches for a value in an m x n matrix.
This matrix has the following properties:

1. Integers in each row are sorted from left to right.
2. 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`


##  <u>Solution 1</u>
_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

```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;
    }
}
```

##  <u>Solution 2</u>
_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

```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;
        
    }
}
```
##  <u>Solution 3</u>
_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`.

 > **4** if `target < matrix[row][col]` then `high = mid-1`

 > **5.** if `target > matrix[row][col]` then `low = mid+1`

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

```java
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;
    }
}
```