240. Search a 2D Matrix II

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.

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, return true.

Given target = 20, return false.

Thoughts:

1. O(mlogn) : iteratively search each row using binary search

2. O(m + n): start at the top right corner. If current number is smaller than target, increase the row number, if it is larger than the target number, decrease the column number, otherwise return False.

Code O(mlogn):

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        def bins(v, target):
            low, high = 0, len(v) - 1
            while(low <= high):
                mid = low + (high - low)/2
                if v[mid] > target:
                    high = mid - 1
                elif v[mid] < target:
                    low = mid + 1
                else:
                    return True
            return False

        m = len(matrix)
        if m == 0:
            return False
        n = len(matrix[0])
        for i in range(m):
            if bins(matrix[i], target):
                return True
        return False

Code O(m + n):

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        m = len(matrix)
        if m == 0: 
            return False
        n = len(matrix[0])
        row , col = 0, n - 1 # top right
        while row < m and col >= 0:
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] < target:
                row = row + 1
            else:
                # matrix[row][col] > target:
                col = col - 1
        return False