Description

Write an efficient algorithm that searches for a value in an m x n matrix. 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.

Solution

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        i = len(matrix) -1
        j = 0
        while i>=0 and j < len(matrix[0]):
            if matrix[i][j]==target:
                return True
            elif matrix[i][j]> target:
                i-=1
            else:
                j+=1
        return False