74. Search a 2D Matrix

Reference: LeetCode EPI 11.6
Difficulty: Medium

Problem

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

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

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

Analysis

Brute-Force

public boolean searchMatrix(int[][] matrix, int target) {
  if (matrix == null || matrix.length == 0) {
    return false;
  }
  int row = matrix.length, col = matrix[0].length;
  for (int r = 0; r < row; ++r) {
    for (int c = 0; c < col; ++c) {
      if (matrix[r][c] == target) {
        return true;
      }
    }
  }
  
  return false;
}

Time: $O(MN)$
Space: $O(1)$

Starting From Corner

Note:

public boolean searchMatrix(int[][] matrix, int target) {
  if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    return false;
  }
  int row = matrix.length, col = matrix[0].length;
  int r = 0, c = col - 1;
  while (r < row && c >= 0) {
    if (matrix[r][c] == target) return true;
    if (target < matrix[r][c]) { // go left
      c -= 1;
    } else { // go down
      r += 1;
    }
  }
  return false;
}

Time: $O(M + N)$
Space: $O(1)$

Binary Search

Learn the conversion between matrix indices and its corresponding list’s index.

Standard Version:

public boolean searchMatrix(int[][] matrix, int target) {
  if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    return false;
  }
  int row = matrix.length, col = matrix[0].length;
  int lo = 0, hi = row * col - 1;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    // convert to row and column
    int r = mid / col;
    int c = mid % col;
    if (matrix[r][c] == target) return true;
    if (matrix[r][c] > target) {
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  return false;
}

Lower Bound Version:

Remember to check boundary before returning.

public boolean searchMatrix(int[][] matrix, int target) {
  if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    return false;
  }
  int row = matrix.length, col = matrix[0].length;
  int lo = 0, hi = row * col - 1;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    int r = mid / col;
    int c = mid % col;
    if (matrix[r][c] >= target) {
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  // remember to check boundary
  return (lo < row * col) && matrix[lo / col][lo % col] == target;
}

Time: $O(\log{MN}) = O(\log{M} + \log{N})$
Space: $O(1)$