I have a x by y matrix, where each row and each column are in ascending order as given below.
1 5 7 9
4 6 10 15
8 11 12 19
14 16 18 21
How to search this matrix for a number in O(x+y)?
I was asked this question for an interview, but could not figure out the way. Curious to know if it could be done.