74. Search a 2D Matrix LeetCode Solution

In this guide, you will get 74. Search a 2D Matrix LeetCode Solution with the best time and space complexity. The solution to Search a D Matrix problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Search a D Matrix solution in C++
Search a D Matrix solution in Java
Search a D Matrix solution in Python
Additional Resources

74. Search a 2D Matrix LeetCode Solution image

Problem Statement of Search a D Matrix

You are given an m x n integer matrix matrix with the following two properties:

Each row is sorted in non-decreasing order.
The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.
You must write a solution in O(log(m * n)) time complexity.

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

Complexity Analysis

Time Complexity: O(mn\log mn)
Space Complexity: O(1)

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

class Solution {
 public:
  bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if (matrix.empty())
      return false;

    const int m = matrix.size();
    const int n = matrix[0].size();
    int l = 0;
    int r = m * n;

    while (l < r) {
      const int mid = (l + r) / 2;
      const int i = mid / n;
      const int j = mid % n;
      if (matrix[i][j] == target)
        return true;
      if (matrix[i][j] < target)
        l = mid + 1;
      else
        r = mid;
    }

    return false;
  }
};
/* code provided by PROGIEZ */

74. Search a 2D Matrix LeetCode Solution in Java

class Solution {
  public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix.length == 0)
      return false;

    final int m = matrix.length;
    final int n = matrix[0].length;
    int l = 0;
    int r = m * n;

    while (l < r) {
      final int mid = (l + r) / 2;
      final int i = mid / n;
      final int j = mid % n;
      if (matrix[i][j] == target)
        return true;
      if (matrix[i][j] < target)
        l = mid + 1;
      else
        r = mid;
    }

    return false;
  }
}
// code provided by PROGIEZ

74. Search a 2D Matrix LeetCode Solution in Python

class Solution:
  def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
    if not matrix:
      return False

    m = len(matrix)
    n = len(matrix[0])
    l = 0
    r = m * n

    while l < r:
      mid = (l + r) // 2
      i = mid // n
      j = mid % n
      if matrix[i][j] == target:
        return True
      if matrix[i][j] < target:
        l = mid + 1
      else:
        r = mid

    return False
 # code by PROGIEZ