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
2
3
4
5
6
7
8
9
[
[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

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 || 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)$

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

Note:

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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.

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

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
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)$


Comment