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

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