Search a 2D Matrix II

Intuition

The top-right cell is special: it is the largest value in its row and the smallest value in its column. That gives a clean decision rule. If the current value is bigger than the target, the entire current column is too big, so drop it by moving left. If the current value is smaller than the target, the entire current row is too small, so drop it by moving down. Each comparison discards one row or one column, so the search converges quickly toward a match or off the edge of the grid.

Algorithm walkthrough

1. 1Start at row = 0 and col = n - 1, the top-right corner.
2. 2Read value = matrix[row][col].
3. 3If value equals target, return true immediately.
4. 4If value is greater than target, decrement col to discard the current column; otherwise increment row to discard the current row.
5. 5Repeat until you fall off the grid, at which point return false.

Implementation

from typing import List


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        row, col = 0, len(matrix[0]) - 1
        while row < len(matrix) and col >= 0:
            value = matrix[row][col]
            if value == target:
                return True
            elif value > target:
                col -= 1
            else:
                row += 1
        return False