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.
For example,
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.
Analysis:
In a 2d array, we can consider it to be a 1d array. Then the mid value should be matrix[mid /col][mid%col]. This could be the key point for this problem. Then compare the value with target.
Time complexity: O(logmn)
Space complexity: O(1)
Below is the code:
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
// O(logmn) binary search
// Corner case
if(matrix == null || matrix.length == 0
|| matrix[0] == null || matrix[0].length == 0) {
return false;
}
int row = matrix.length;
int col = matrix[0].length;
int start = 0;
int end = row * col - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
// Key point, the index is mid/col and mid%col
int num = matrix[mid / col][mid % col];
if (num == target) {
return true;
} else if (num < target) {
start = mid;
} else {
end = mid;
}
}
if (matrix[start / col][start % col] == target) {
return true;
} else if (matrix[end / col][end % col] == target) {
return true;
}
return false;
}
}
Followup:
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.
For 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.
Analysis:
This problem is different from the first one. So in this case, we can’t use the first method to transfer from a 2d array to a 1d array.
However, we can still use the method similar to the binary search. Basically, we can go from the left bottom and consider it to be the mid value. Or we can go from the up right corner. In the code below, we choose from the left bottom.
If it equals to the target, we find it
If it’s larger than the target, we should move up
If it’s less than the target, we should move right
This is the trick part in this problem.
Time complexity: O(m + n)
Space complexity: O(1)
The code is below:
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
// O(m + n) Similar to binary search
// Corner case
if (matrix == null || matrix.length == 0 ||
matrix[0] == null || matrix[0].length == 0) {
return false;
}
int row = matrix.length;
int col = matrix[0].length;
// Start from left bottom
int x = row - 1;
int y = 0;
while (x >= 0 && y <= col - 1) {
int num = matrix[x][y];
if (num == target) {
return true;
} else if (num < target) {
// Move right
y++;
} else {
// Move up
x--;
}
}
return false;
}
}
CodeBySteven 