Search a row and column sorted matrixHard
matrixof numbers of size
m x n, and a
targetnumber, write a function that determines if the
targetnumber exists in the
Every row and every column is sorted in ascending order in the given
For example, if your function recieves the following 3x3 matrix and target number:
matrix = [[1, 3, 8, 10],[2, 5, 9, 11],[3, 6, 10, 15],[5, 7, 12, 18],]target = 6
Your function should return
Given the same matrix, if the
4, your function should return
Note how in
matrix, every row and column is sorted, but is not necessarily greater than the previous row or column.
Before you look at the solution, try to code it yourself.
Time and Space Complexity
On each iteration we either remove an entire row or an entire column.
Therefore, our time complexity is
O(m + n).
There is no additional space required. So the space complexity constant