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:

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

Analysis

Brute-Force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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)$

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

Standard Version:

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 == 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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)$


Comment