Medium · Staircase Search
Understand → Visualise → Practice.
Rows and columns are ascending. Return whether `target` occurs in the non-empty matrix.
At the top-right corner, moving left decreases values and moving down increases them, so each comparison eliminates a whole column or row.
row = 0, col = last column.
Equal: found. Too big: move left (the column below is even bigger). Too small: move down.
Leaving the matrix means the target is absent.
O(rows + cols) time and O(1) space.
Ordinary binary search over flattened indices requires a stronger global row-order condition.
Read the full guide first: Matrices and 2-D Arrays.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.