240.Search a 2D Matrix II

Posted on | In

Test cases

1
2
3
4
5
6
7
8
9
10
[[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]]
4
[[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]]
30
[]
0
[[1]]
1
[[]]
0

Solution 1: accepted 18ms

Binary search for each row.

Time: O(nlogn)
Space: O(1) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public boolean searchMatrix(int[][] matrix, int target) {       
    int m = matrix.length - 1;
    if (m < 0) return false;
    int n = matrix[0].length - 1;
    if (n < 0) return false;
    for (int i = 0; i <= m; i++) {
      if (target < matrix[i][0] || target > matrix[i][n]) {
          continue;
      } else {
        // Binary search for each row
        int lo = 0;
        int hi = n;
        while (lo <= hi) {
          int mid = lo + (hi - lo) / 2;
          if (target > matrix[i][mid]) {
            lo = mid + 1;
          } else if (target < matrix[i][mid]) {
            hi = mid - 1;
          } else {
            return true;
          }
        }
        if (matrix[i][lo] == target)
            return true;
      }
    } 
    return false;
}

Solution 2: accepted 13ms

Seach from top-right or bottom left.

Time: O(nm)
Space: O(1) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean searchMatrix(int[][] matrix, int target) {   
  if (matrix.length < 1 || matrix[0].length < 1) 
      return false;
  int m = martrix.length;
  int n = matrix[0].length;
  int row = m - 1;
  int col = 0;
  while (row >= 0 && col < n) {          
    if (matrix[row][col] > target) {
      row--;
    } else if (matrix[row][col] < target) {
      col++;
    } else {
      return true;
    }
  } 
  return false;
}

Follow-up: if every row is straightly ascending (the first element of this row is larger than the last element in last row), the complexity could be O(logM+logN). Treate it as a 1D array, do a binary search (row = mid/column, col = mid%column).