Search in a 2D matrix
VisaThe problem
Given a 2-D array mat where the elements of each row are sorted in non-decreasing order, and the first element of a row is greater than the last element of the previous row (if it exists), and an integer target, determine if the target exists in the given mat or not.
Input: mat = [ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12] ], target = 8 Output: True Explanation: The target = 8 exists in the 'mat' at index (1, 3).
Input: mat = [ [1, 2, 4], [6, 7, 8], [9, 10, 34] ], target = 78 Output: False Explanation: The target = 78 does not exist in the 'mat'. Therefore in the output, we see 'false'.
Input: mat = [ [1, 2, 4], [6, 7, 8], [9, 10, 34] ], target = 7
- n == mat.length
- m == mat[i].length
- 1 <= m, n <= 100
- -104 <= mat[i][j], target <= 104
cpp
class Solution{
public:
bool searchMatrix(vector<vector<int>> &mat, int target){
}
};java
class Solution {
public boolean searchMatrix(int[][] mat, int target) {
}
}python
class Solution:
def searchMatrix(self, mat, target):javascript
class Solution {
searchMatrix(mat, target) {
}
}csharp
class Solution
{
public bool SearchMatrix(List<List<int>> mat, int target)
{
// Write your code here
}
}go
func searchMatrix(mat [][]int, target int) bool {
}Stuck? Show a way to structure it+
- 01Treat the matrix as a sorted array of length m*n.
- 02Binary-search indices from 0 to m*n-1.
- 03Map an index to row and column with division and modulo.
- 04Compare and narrow normally.
- 05Handle empty dimensions first.
Reference answer
Then expect these follow-ups
How do you solve the row-and-column sorted version?
Tests: staircase search
How do duplicates affect the result?
Tests: binary search
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question