26. Search a 2D Matrix

MediumBinary SearchAlso on LeetCode ↗

Each row of matrix is sorted, and the first value of every row is greater than the last value of the row above. Return whether target exists, in O(log(m·n)).

Example 1

Input: matrix = [[1,4,7],[10,13,16],[20,22,25]], target = 13

Output: true

Example 2

Input: matrix = [[1,4,7],[10,13,16],[20,22,25]], target = 15

Output: false

Hint 1

Reading the rows one after another gives a single sorted array of length m·n.

Hint 2

Index k maps to row k / n, column k % n.

Binary SearchMatrix

Reference solution for Flattened binary search (time O(log(m·n)), space O(1)). Each solution passes every test in all four languages.

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        lo, hi = 0, m * n - 1                 # treat the matrix as one sorted array
        while lo <= hi:
            mid = (lo + hi) // 2
            v = matrix[mid // n][mid % n]
            if v == target:
                return True
            if v < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return False

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length, lo = 0, hi = m * n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2, v = matrix[mid / n][mid % n];
            if (v == target) return true;
            if (v < target) lo = mid + 1; else hi = mid - 1;
        }
        return false;
    }
}

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

function searchMatrix(matrix, target) {
  const m = matrix.length, n = matrix[0].length;
  let lo = 0, hi = m * n - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1, v = matrix[Math.floor(mid / n)][mid % n];
    if (v === target) return true;
    if (v < target) lo = mid + 1; else hi = mid - 1;
  }
  return false;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Language

26. Search a 2D Matrix

Example 1

Example 2

Approach 1: Row then column

Approach 2: Flattened binary search ✅