Generated by Codex with GPT-5

Quick facts

Problem gist

The matrix is sorted in two directions at once. Every row is sorted from left to right, and every column is sorted from top to bottom. Given a target value, the task is to decide whether the target appears anywhere in the matrix.

The important detail is that this is not the same as LeetCode 74, where the matrix can be treated like one fully sorted one-dimensional array. Here, the end of one row is not guaranteed to be smaller than the start of the next row. The matrix has partial order, not total order.

A brute-force scan checks every cell in O(m * n) time. A row-by-row binary search improves that to O(m log n), but it still misses the stronger structure created by the sorted columns.

Deriving the optimal solution

The clean solution starts from a corner where one move can eliminate a whole row or a whole column. The top-right corner is ideal:

If matrix[row][col] equals the target, the search is done.

If matrix[row][col] is greater than the target, everything below it in the same column is also greater, because columns are sorted downward. The target cannot be in that column, so move left.

If matrix[row][col] is less than the target, everything to its left in the same row is also smaller, because rows are sorted left to right. The target cannot be in that row, so move down.

Each comparison removes one row or one column from consideration. There is no backtracking because the sorted directions prove the discarded region cannot contain the target. Starting at the bottom-left corner works symmetrically: move up when the current value is too large, and move right when it is too small.

Python solution

from typing import List


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        """
        Return True if target exists in a matrix sorted by rows and columns.

        The search starts at the top-right corner. From there, each comparison
        removes either the current column or the current row.
        """
        if self._is_empty(matrix):
            return False

        row = 0
        column = len(matrix[0]) - 1

        while row < len(matrix) and column >= 0:
            current_value = matrix[row][column]

            if current_value == target:
                return True

            if current_value > target:
                column -= 1
            else:
                row += 1

        return False

    @staticmethod
    def _is_empty(matrix: List[List[int]]) -> bool:
        return not matrix or not matrix[0]

Complexity

The search visits at most one cell per eliminated row or column, so the time complexity is O(m + n) for an m by n matrix.

The algorithm uses O(1) extra space. It only stores the current row, current column, and current cell value.

Interview follow-ups

Why start from the top-right or bottom-left corner?

The chosen corner must give two useful directions after each comparison. At the top-right corner, moving left makes values smaller, and moving down makes values larger. That means a comparison with the target tells the algorithm exactly which entire line can be discarded.

The top-left corner does not work the same way. If the top-left value is too small, both moving right and moving down lead to larger values, so neither direction can safely eliminate the other. The bottom-right corner has the opposite problem when the value is too large. The top-right and bottom-left corners are special because their two outgoing directions move in opposite value directions.

What if only each row is sorted, but columns are not sorted?

The staircase method depends on both row and column ordering. If columns are not sorted, moving down from the top-right corner no longer has a predictable effect, so the algorithm cannot discard a full row safely.

The expected solution becomes binary search on each row. For every row, first check whether the target is within that row’s minimum and maximum values, then binary-search that row if it is a possible match. The worst-case time is O(m log n), and the extra space is O(1). Range checks can skip some rows in practice, but they do not improve the worst case unless more structure is guaranteed.

What if the interviewer asks for the target coordinates?

The same staircase search can return coordinates instead of a boolean. When the current cell equals the target, return (row, column). If the loop finishes without a match, return a sentinel such as (-1, -1) or None, depending on the requested API.

The reasoning and complexity do not change. The algorithm is still eliminating one row or column per step, so it remains O(m + n) time and O(1) space. If duplicates are allowed and the interviewer wants all coordinates, then the problem changes: one match is no longer enough, and the output itself may contain many cells.

What if duplicates exist and the task is to count how many times target appears?

For integer matrices sorted by rows and columns, a useful approach is to count how many values are <= target and subtract how many values are < target. Each count can be computed in O(m + n) with a bottom-left or top-right sweep.

For example, from the bottom-left corner, if the current value is <= x, then every value above it in that column is also <= x, so add row + 1 cells and move right. If the current value is greater than x, move up. Then the exact number of target values is count_less_or_equal(target) - count_less_or_equal(target - 1).

This keeps the count operation at O(m + n) time and O(1) space for integer targets. The tradeoff is that it solves a counting problem, not a coordinate-listing problem. Returning every matching coordinate still costs O(k) output space for k matches.

What if the matrix receives frequent updates?

The given sorted-matrix structure is designed for fast search on mostly static data. Arbitrary updates are hard because changing one cell can violate row and column order, and repairing that order may require moving many values.

If the interview turns into a dynamic membership problem, the better data structure depends on the operation mix. For many updates and simple existence queries, a hash set gives average O(1) insert, delete, and lookup, but it discards sorted order. If sorted queries such as rank, range count, or nearest value are required, a balanced search tree or indexed structure is more appropriate, usually with O(log n) operations and more implementation complexity. The key tradeoff is whether the matrix ordering itself is still required or whether the real requirement is just fast membership.