Search for a Target in a Matrix Sorted by Rows and Columns

Given a matrix of integers in which every row is sorted in non-decreasing order from left to right and every column is sorted in non-decreasing order from top to bottom, determine whether a target value appears anywhere in the matrix.

Function Signature

search_sorted_matrix(matrix: list[list[int]], target: int) -> bool

Rules

• Return True if at least one cell equals target, and False otherwise.
• Values may repeat within a row, within a column, or across the matrix.
• A row does not have to start after the previous row ends: the first value of a row may be smaller than the last value of the row above it.

Constraints

• matrix has m rows and n columns, with 1 <= m <= 300 and 1 <= n <= 300; every row has length n.
• Every element and target is an integer in [-1000000000, 1000000000].
• The intended solution does not examine every cell.

Examples

Input: matrix = [[1,4,7,11],[2,5,8,12],[3,6,9,16],[10,13,14,17]], target = 9

Output: True

Input: matrix = [[1,4,7,11],[2,5,8,12],[3,6,9,16],[10,13,14,17]], target = 15

Output: False

Input: matrix = [[-5,-5,0]], target = 1

Output: False

Search a Row-and-Column Sorted Matrix

You are given a matrix of integers in which every row is sorted in non-decreasing order from left to right and every column is sorted in non-decreasing order from top to bottom. Given an integer target, determine whether target appears anywhere in the matrix.

Return True if at least one cell of the matrix equals target, and False otherwise. The answer is a single boolean, so there is no ordering or tie-breaking to decide: duplicates do not change the result, because you only report existence and never a position.

Values may repeat within a row, within a column, or across the matrix. A row does not have to start after the previous row ends: the first value of a row may be smaller than the last value of the row above it, so reading the matrix row by row into one flat list does not necessarily produce a sorted list.

The intended solution does not examine every cell.

Every element and target lies in [-1000000000, 1000000000], so no value can exceed 2^31 - 1 and no arithmetic on these values is required; a 32-bit signed integer is sufficient in every language (Java int, C++ int).

Examples

Example 1:

matrix = [[1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16], [10, 13, 14, 17]]
target = 9
-> True

The cell at row 2, column 2 holds 9, so the target is present. Note that this matrix illustrates the overlap rule: row 1 starts at 2, which is smaller than 11, the last value of row 0.

Example 2:

matrix = [[1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16], [10, 13, 14, 17]]
target = 15
-> False

The matrix contains 14 and 16 but no 15, so the answer is False.

Example 3:

matrix = [[-5, -5, 0]]
target = 1
-> False

A single row with a duplicated value and no cell above 0.

Hints

1. Both sorted properties hold at the same time. Ask what a single comparison against one well-chosen cell can rule out: is there a starting position from which one comparison eliminates an entire row or an entire column of candidates?
2. Reading the cells row by row into one flat list does not give you a sorted list, because a row may begin below where the previous row ended. Any approach that assumes a single global order over all cells is unsound on this input.
3. You only have to report whether the value exists, not where it is or how many times, so repeated values never need to be disambiguated.

Approach

Algorithm (staircase / saddle-point walk). Because each row is sorted left to right and each column is sorted top to bottom, the top-right cell of any sub-rectangle is the largest value in its row of that rectangle and the smallest value in its column of that rectangle. Start at row = 0, col = n - 1 and compare matrix[row][col] with the target:

• equal: the target exists, return True;
• greater than the target: every cell below it in column col is >= it, hence also greater than the target, so no occurrence of the target can be in that column; drop the column with col -= 1;
• less than the target: every cell to its left in row row is <= it, hence also less than the target, so no occurrence of the target can be in that row; drop the row with row += 1.

Invariant: before each comparison, if the target occurs anywhere in the matrix then it occurs inside the sub-rectangle rows [row, m-1] x columns [0, col]. It holds trivially at the start (the whole matrix). Each step removes exactly one full column or one full row that provably contains no occurrence of the target, so the invariant is preserved and no occurrence is ever skipped.

Correctness: the loop can only exit in two ways. If it returns True, it has seen a cell equal to the target, so the answer is genuinely True. If it exits because row == m or col < 0, the surviving rectangle is empty, and by the invariant the target occurs nowhere in the matrix, so False is correct.

Termination and complexity: every iteration either increases row by one or decreases col by one, both bounded, so at most m + n - 1 cells are inspected. Time is O(m + n) and space is O(1) beyond the input, which satisfies the requirement that the intended solution does not examine every cell.

Duplicates: the walk decides existence only. If several cells hold the target, the first one the staircase reaches returns True; the order in which equal values are visited is irrelevant to the boolean answer.

Edge cases: a 1x1 matrix performs a single comparison; a single row (m = 1) degenerates into a right-to-left scan because the walk can only move left before falling off the left edge or matching; a single column (n = 1) only moves down; a matrix whose cells are all equal returns on the first comparison when it matches and otherwise walks one full edge; a target below the global minimum exits off the left edge and a target above the global maximum exits off the bottom edge. A row whose first value is smaller than the previous row's last value is handled naturally, since the argument above only uses within-row and within-column order, never a flattened global order. The reference implementations also guard an empty matrix or an empty first row by returning False, even though the constraints guarantee m >= 1 and n >= 1.

• Time complexity: O(m + n)
• Space complexity: O(1)