240. Search a 2D Matrix II

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 in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
Given target = 5, return true
Given target = 20, return false

Analysis

Brute-Force

public boolean searchMatrix(int[][] matrix, int target) {
  if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    return false;
  }
  int row = matrix.length;
  int 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)$

Binary Search

Iterate over elements along the diagonal, and each time perform binary search horizontally and vertically.

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 = 0;
  while (r < row && c < col) { // min(M, N)
    if (bsHelper(matrix, r, c, target)) return true;
    r += 1;
    c += 1;
  }    
  return false;
}

private boolean bsHelper(int[][] matrix, int r, int c, int target) {
  int row = matrix.length;
  int col = matrix[0].length;
  if (r >= row || c >= col) {
    return false;
  }
  // horizontal
  int lo = c, hi = col - 1;
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (matrix[r][mid] == target) return true;
    if (matrix[r][mid] > target) {
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  // vertical
  lo = r; hi = row - 1; // semicolon
  while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (matrix[mid][c] == target) return true;
    if (matrix[mid][c] > target) {
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  return false;
}

Time: $O(N\log{M})$ or $O(M\log{N})$
Space: $O(1)$

Search Space Reduction

Start from the corner up-right or bottom-left.

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

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

Divide and Conquer

Marked. I don’t quite really understand.

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;
  return searchRect(matrix, target, 0, 0, col - 1, row - 1);
}

private boolean searchRect(int[][] matrix, int target, int left, int up, int right, int down) {
  if (left > right || up > down) {
    return false; // this submatrix has no height or no width
  }
  if (target < matrix[up][left] || target > matrix[down][right]) {
    return false; // "target" is already larger than the largest or the smallest element
  }
  int mid = left + (right - left) / 2;
  // Locate "row" such that matrix[row - 1][mid] < target < matrix[row][mid]
  int row = up;
  while (row <= down && matrix[row][mid] <= target) {
    if (matrix[row][mid] == target) {
      return true;
    }
    row += 1;
  }
  return searchRect(matrix, target, left, row, mid - 1, down) || searchRect(matrix, target, mid + 1, up, right, row - 1);
}

Time: $O(N\log{N})$
Space: $O(1)$