Leetcode Search a 2D Matrix problem solution

YASH PAL,

In this Leetcode Search, a 2D Matrix problem solution 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.
Leetcode Search, a 2D Matrix problem solution

Problem solution in Python.

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False

        row = []
        # store the row with great or equal value to the target
        for record in matrix:
            if record[-1] >= target:
                row = record
                break
        
        # iterate through the row until you find the target
        for element in row[::-1]:
            if element == target:
                return True

        return False

Problem solution in Java.

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {

        //corner case
        if(matrix == null || matrix.length == 0) return false;
        if(matrix[0] == null || matrix[0].length == 0) return false;

        int r = matrix.length;
        int c = matrix[0].length;

        int left = 0;
        int right = r * c - 1;

        while(left <= right){
            int mid = left + (right - left)/2;

            int value = matrix[mid / c][mid % c];

            if(value == target){
                return true;
            }
            else if(value < target)

                left = mid + 1;
            else
                right = mid -1;
        }
        return false;
    }
}

Problem solution in C++.

class Solution {
public:
    bool searchMatrix(vector <vector<int> >& matrix, int target) {
        int row = matrix.size(), col = matrix[0].size();
        int left = 0, right = row * col - 1;
        while (left <= right)
        {
            int mid = left +(right - left)/2;
            int r = mid / col, c = mid % col;
            if (matrix[r][c]==target) return true;
            if (matrix[r][c] < target)
                left = mid +1;
            else
                right = mid -1;
        }
        return false;
    }
};

Problem solution in C.

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){
    int totalRow=matrixSize;
    if(totalRow==0 || *matrixColSize==0)
    {
        return false;
    }
    
    int start=0;
    int end=matrixSize*(*matrixColSize)-1;
    int row=0;
   
    int col= 0;
   
    int mid=0;
    
    while(start<=end)
    {
        mid=(start+end)/2;
        
        row=mid/(*matrixColSize);
        
        col=mid%(*matrixColSize);
        
        
        if(matrix[row][col]==target)
        {
            return true;
        }
        
        else if(matrix[row][col]>target)
        {
            end=mid-1;
        }
        
        else
        {
            start=mid+1;
        }
    }
    
    return false;
}

coding problems