Leetcdoe 74. Search a 2D Matrix

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

We can use built-in function, or search from top-right or bottom-left corner.

Solution 1:

# T:O(n) S:O(1)
class Solution:
    # @param {integer[][]} matrix
    # @param {integer} target
    # @return {boolean}
    def searchMatrix(self, matrix, target):
        for i in xrange(len(matrix)):
            if target in matrix[i]:
                return True
        else:
            return False

Run Time: 40 ms

Solution 2:

# T:O(m + n) S:O(1)
class Solution:
    # @param {integer[][]} matrix
    # @param {integer} target
    # @return {boolean}
    def searchMatrix(self, matrix, target):
        m, n = len(matrix), len(matrix[0])
        i, j = 0, n - 1
        while i < m and j > -1:
            if matrix[i][j] < target:
                i += 1
            elif matrix[i][j] > target:
                j -= 1
            else:
                return True
        else:
            return False

Run Time: 52 ms