In this post, we are going to solve the 74. Search a 2D Matrix problem of Leetcode. This problem 74. Search a 2D Matrix is a Leetcode medium level problem. Let’s see the code, 74. Search a 2D Matrix – Leetcode Solution.

Problem

Write an efficient algorithm that searches for a value target in an m x n integer matrix 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.

Example 1 :

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

Example 2 :

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

Constraints

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

Now, let’s see the code of 74. Search a 2D Matrix – Leetcode Solution.

Search a 2D Matrix – Leetcode Solution

74. Search a 2D Matrix – Solution in Java

class Solution {
    
    public boolean bs(int[][] matrix,int row, int start, int end, int target){
        while(start <= end){
            int mid = start - ( start - end) / 2;
            if(target == matrix[row][mid]) return true;
            else if(target < matrix[row][mid]) end = mid-1;
            else if(target > matrix[row][mid]) start = start + 1;
        }
        return false;
    }
    public boolean searchMatrix(int[][] matrix, int target) {
        
        //finding potential row
        int m = matrix[0].length-1;
        int sRow = 0;
        int eRow = matrix.length-1;
        while(sRow <= eRow){
            int mid = sRow - (sRow - eRow)/2;
            if(target == matrix[mid][0] || target == matrix[mid][m]) return true;
            else if(target > matrix[mid][0] && target < matrix[mid][m]){
                return bs(matrix, mid, 0, m, target);
            }
            else if(target < matrix[mid][0]){
                eRow = mid - 1;
            }
            else if(target > matrix[mid][m]){
                sRow = mid + 1;
            }
        }
        
        
        return false;
    }
    
    
}

74. Search a 2D Matrix – Solution in C++

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n = matrix.size();
        int m = matrix[0].size();
        
        if(n == 0 || m == 0)
            return false;
        
        int start = 0, end = m*n - 1;
        
        while(start <= end)
        {
            int mid = start + (end - start) / 2;
			
            int ind = matrix[mid/m][mid%m];
            if (target == ind)
                return true;
			
            else if(target < ind)
                end = mid - 1;
            else
			
                start = mid + 1;       
        }
        return false;
    }
};

74. Search a 2D Matrix – Solution in Python

class Solution:
    def searchMatrix(self, matrix, target):
        if not matrix or not matrix[0]: return False
        m, n = len(matrix[0]), len(matrix)
        beg, end = 0, m*n - 1
        while beg < end:
            mid = (beg + end)//2
            if matrix[mid//m][mid%m] < target:
                beg = mid + 1
            else:
                end = mid
        return matrix[beg//m][beg%m] == target

Note: This problem 74. Search a 2D Matrix is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.