Leetcode 0074 Search 2d Matix
Meta Data
Link
Tags
Similar
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
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Solution Approaches
O(N * M) Brute Force Linear Search
- Traverse through the entire matrix and check
- Basically Linear Search Algorithm
O(N * Log(M)) Binary Search Row Wise
- As rows are sorted perform Binary Search Algorithm on each
- If
target
is not found at the end of search then move to the next row - Time for binary search is
log M
which is applied onN rows
soO(N * Log(M))
in total.
O(Log(N * M)) sO(1) Binary Search Entire
- First Element of each row is greated than last element of previous
- By the above property we can simply vizualize the this 2D matrix to be sorted 1D matrix
- If we can associate approriate indexes of that 1D matix to 2D then we this problem simplies to a plain Binary Search Algorithm
- Indexes of 1D matrix are of formed by
mat2D[i][j] = mat1D[i*(n) + j]
| (i,j) | 0 | 1 | 3 | 3 | 4 |
| ----- | ----- | ----- | ----- | ----- | ----- |
| 0 | (0,0) | (0,1) | (0,2) | (0,3) | (0,4) |
| 1 | (1,0) | (1,1) | (1,2) | (1,3) | (1,4) |
| 2 | (2,0) | (2,1) | (2,2) | (2,3) | (2,4) |
| 3 | (3,0) | (3,1) | (3,2) | (3,3) | (3,4) |
| (n * i + j) | 0 | 1 | 3 | 3 | 4 |
| ----------- | --- | --- | --- | --- | --- |
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 5 | 6 | 7 | 8 | 9 |
| 2 | 10 | 11 | 12 | 13 | 14 |
| 3 | 15 | 16 | 17 | 18 | 19 |
int getval(vector<vector<int>> &matrix, int mid){
int n = (matrix[0].size());
return matrix[mid/n][mid%n];
}
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int low = 0;
int high = matrix.size() * matrix[0].size() - 1 ;
while (low <= high) {
int mid = (low + high) / 2;
int midval = getval(matrix, mid);
if (midval == target) {return true;}
else if (midval < target) {
low = mid + 1;
}
else {
high = mid-1;
}
}
return false;
}
Return to DSA