Search a 2D Matrix II
Problem is here: https://leetcode.com/problems/search-a-2d-matrix-ii/description/
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 =
The trick is actually to start the search from the top right corner: if the target is equal to that cell, great, otherwise either move to the left or down for a total of O(m+n)-time and no extra space. Cheers, Marcelo.20, return false.
public class Solution
{
public bool SearchMatrix(int[,] matrix, int target)
{
if (matrix == null || matrix.GetLength(0) == 0 || matrix.GetLength(1) == 0) return false;
int R = matrix.GetLength(0);
int C = matrix.GetLength(1);
int r = 0;
int c = C - 1;
while (r < R && c >= 0)
{
if (matrix[r, c] == target) return true;
else if (matrix[r, c] > target) c--;
else r++;
}
return false;
}
}
I had this question on my very first interview with Microsoft and looks like we have almost identical solutions :)
ReplyDeleteclass Solution {
public:
bool searchMatrix(vector>& matrix, int target) {
if (matrix.empty()) return false;
int row = 0;
int column = matrix[0].size()-1;
while (row < matrix.size() && column >= 0) {
int current_value = matrix[row][column];
if (current_value == target) {
return true;
} else if (target < current_value) {
column -= 1;
} else {
row += 1;
}
}
return false;
}
};
Cheers,
Taras
Cool! I’m torn about this question, it does seem a little tricky to me, although once you get the solution, it does look intuitive and clever
ReplyDeleteagreed, it's also a bit tricky since "sorted" keyword immediately triggers desire to use binary search :)
Delete