Search a Row-and-Column Sorted Matrix
You get a matrix matrix of integers and an integer target.
Every row is sorted in ascending order from left to right, and every column is sorted in ascending order from top to bottom. Values can repeat.
Return true if target is somewhere in the matrix, and false if it is not.
Note
The last value of a row can be bigger than the first value of the next row. So you cannot treat the matrix as one long sorted list.
Hint: start at the top-right corner. Every value to its left is smaller or equal, and every value below it is bigger or equal. Each comparison lets you drop a whole row or a whole column, so the search takes O(r + c) steps.
Examples
Example 1
- Input:
- [[2,6,11,15],[4,8,13,19],[9,12,17,24]], 13
- Output:
- true
13 is in row 1, column 2.
Example 2
- Input:
- [[2,6,11,15],[4,8,13,19],[9,12,17,24]], 10
- Output:
- false
10 is between some values of the matrix, but no cell holds 10.
Example 3
- Input:
- [[-5]], -5
- Output:
- true
The only cell holds -5, which is the target.
Constraints
1 <= r, c <= 8(the matrix hasrrows andccolumns)-200 <= matrix[i][j], target <= 200- Every row and every column is sorted in ascending order.
Run checks your code against the 3 examples. Submit checks it against all 223 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.