Skip to main content

240. Search a 2D Matrix II

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

Python​

Binary Search on cols​

  • Time: O(logm * logn)
  • Space: O(1)
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        n = len(matrix)
        m = len(matrix[0])

        for col in range(m):
            top, down = 0, n-1
            while top <= down:
                cur = (top+down)//2
                if matrix[cur][col] == target:
                    return True
                elif matrix[cur][col] < target:
                    top = cur + 1
                else:
                    down = cur - 1

        return False

Divide and Conquer​

Start from top right, and:

  1. If target > value, target not possible in the next rows of the column
  2. If target < value, target not possible in the right of the row

(Can also start from the bottom left field)

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        n = len(matrix)
        m = len(matrix[0])

        # row: 0 ~ n-1
        # col: m-1 ~ 0
        row, col = 0, m-1

        while row < n and col >= 0:
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] > target:
                col -= 1
            else:
                row += 1
        return False