## DEV Community 👩‍💻👨‍💻 is a community of 932,977 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

sachin26

Posted on • Updated on

# Striver's SDE Sheet Journey - #13 Search in a 2d Matrix

Problem Statement :-

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`

## 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.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`.

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`.

``````class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int n = matrix.length;
int m = matrix.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;
}
}
``````

## 🌙 Dark Mode?!

Turn it on in Settings