240 Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an mxnmatrix. 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.

For 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, returntrue.

Given target=20, returnfalse.

The Idea: Zig zag through the matrix (eliminate rows and columns) until we either find or exceed the bounds of the matrix. If we start from the upper right corner, we can deduce two things. First, since the else element of every row contains the max element of the row it is under, if that target is greater than that element, then no other element in the row are guaranteed to match it. Therefore the only option is to move down one row, where this element is greater than it. Secondly, if the element is otherwise smaller than the target, then we can deduce that the elements in the column beneath it are all greater. So likewise, the only option would be to move left.

Complexity: O(n+m) time. Consider the worst case occurance of the element on the bottom-left. O(1) space.

def searchMatrix(self, matrix, target):
    """
    :type matrix: List[List[int]]
    :type target: int
    :rtype: bool
    """

    if len(matrix) == 0 or (len(matrix) == 1 and len(matrix[0]) == 0):
        return False

    rows = len(matrix)
    cols = len(matrix[0])

    r = 0
    c = cols - 1

    while c >= 0 and r < rows:
        if matrix[r][c] < target:
            r += 1
        elif matrix[r][c] > target:
            c -= 1
        else:
            return True

    return False