Search in 2D Matrix Explanation

There are two similar problems related to search a value in 2D matrix. Let us see them.

74. Search a 2D Matrix

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:

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

240. Search a 2D Matrix II

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:

Consider the following matrix:

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

Explanation

So, what is the difference between these two problems?

For the first problem, every row is sorted and the current rows values are guaranteed to be greater than the preceding rows. So the whole matrix can be seen as a sorted array. The solution can be just search in a sorted 1D array, with binary sarch. The key is to translate the index into 2D.

As for the second problem, every row is sorted and every col is sorted. However, the values in preceding rows are not necessarily greater than the following rows. So we cannot do better than linear search. We can start from the top-right, and if the current value is greater than the target value, we have to search in the current row; else if the current value if less than the target value, we have to go down.

Solution

Code for 71

Time complexity: O(log(mn))
Space complexity: 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
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) return false;

int m = matrix.length;
int n = matrix[0].length;
int lo = 0;
int hi = m * n - 1;

while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int midValue = matrix[mid / n][mid % n];

if (midValue == target) {
return true;
}

if (midValue < target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}

return false;
}

Code for 240

Time complexity: O(m + n)
Space complexity: O(1)

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) return false;

int row = matrix.length;
int col = matrix[0].length;

int i = 0, j = col - 1;
while (i < row && j >= 0) {
if (matrix[i][j] == target) {
return true;
} else if (target > matrix[i][j]) {
i++;
} else if (target < matrix[i][j]) {
j--;
}
}

return false;
}