0000 - 0099
0074 - Search a 2D Matrix (Medium)
Problem Link
https://leetcode.com/problems/search-a-2d-matrix/
Problem Statement
Write an efficient algorithm that searches for a value target in an m x n integer matrix 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,60]], target = 3
Output: trueExample 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: falseConstraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-10^4 <= matrix[i][j], target <= 10^4
Approach 1: Searching Row & Column
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int n = matrix.size(), m = matrix[0].size();
int targetRow = 0;
// search for the target row
for (int row = 0; row < n; row++) {
// target should be within [matrix[row][0] .. matrix[row][m - 1]]
if (matrix[row][0] <= target && target <= matrix[row][m - 1]) {
// target row is found
targetRow = row;
break;
}
}
// then search for the target col
for (int col = 0; col < m; col++) {
if (matrix[targetRow][col] == target) {
return true;
}
}
return false;
}
};Approach 2: Binary Search
Find which row and coloumn the element belongs to by using Binary Search
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
for (int i = 0; i < matrix.length; i++) {
int low = 0;
int high = matrix[i].length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (matrix[i][mid] == target) {
return true;
} else if (matrix[i][mid] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
}
return false;
}
}