https://leetcode.com/problems/search-a-2d-matrix-ii

Let us consider the following example and discuss the algorithm.

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

Let us start with element on the top right corner and on each step we decide where we can go.

  1. Current number is equal to 15, and target = 5, where can we go? All numbers above 15 is more than 15, so we can eliminate last column and go to the left.
  2. Current number is equal to 11 and again it is bigger than target = 5, so we eliminate column and go to the left
  3. Current number is equal to 7, go to the left.
  4. Current number is 4, now it is smaller than target, so we can eliminate first row: elements to the left is smaller than 4 and elements to the right already eliminated in columns.
  5. Current number is 5 and we found our target.

It also can happen, that we do not found number, in this case we need to terminate, when we can not move anymore.

Complexity: time complexity is O(m + n), where m, n are number of columns and rows: on each step we eliminate either row or column. Space complexity is O(1).

class Solution:
    def searchMatrix(self, matrix, target):
        x, y = len(matrix[0]) - 1, 0
        while x >= 0 and y < len(matrix):
            if matrix[y][x] > target:
                x -= 1
            elif matrix[y][x] < target:
                y += 1
            else:
                return True
        return False

If you like the solution, you can upvote it on leetcode discussion section: Problem 0240