Search in a Sorted 2D Matrix (Staircase Search)

You are given an m x n matrix in which every row is sorted in strictly increasing order from left to right and every column is sorted in strictly increasing order from top to bottom. Unlike a fully row-major sorted matrix, the last element of one row is not necessarily smaller than the first element of the next row. Given a target value, determine whether it exists anywhere in the matrix using a staircase search that starts at the top-right corner and eliminates an entire row or column at every step.

Input: The first line contains two integers m and n. Each of the next m lines contains n space-separated integers, the matrix rows. The final line contains the integer target. Output: Print "YES" if the target exists in the matrix, otherwise print "NO".

1 <= m, n <= 1000 -10^9 <= matrix[i][j] <= 10^9 -10^9 <= target <= 10^9 Each row is strictly increasing left to right; each column is strictly increasing top to bottom.

This is a genuinely DIFFERENT problem from 'Search in a Row-and-Column Sorted 2D Matrix' (where rows continue seamlessly from each other) - that version reduces to a flat sorted array, while THIS version (rows/columns sorted independently, no cross-row guarantee) specifically needs the staircase technique instead.

Search for a target in a matrix where rows and columns are each sorted independently, but rows don't necessarily continue from each other. Brute force: Scan every cell of the matrix directly, or run a separate binary search on each row - this costs O(m*n) or O(m log n) respectively, more than necessary given the matrix's dual row-and-column sortedness. Optimised: Starting from the TOP-RIGHT corner (a specific choice, not arbitrary) means one direction (down) always increases values and the other (left) always decreases them - this lets every single comparison ELIMINATE an entire row or column at once, achieving the search in linear time relative to the matrix's dimensions rather than its total cell count.

1. Start at the TOP-RIGHT corner, where moving DOWN strictly increases values and moving LEFT strictly decreases them. 2. If the current cell is BIGGER than the target, the entire COLUMN below it can be discarded (move left). 3. If the current cell is SMALLER than the target, the entire ROW to its left can be discarded (move down).

Time: O(m + n) - at most m+n steps, since each step eliminates either a full row or a full column. Space: O(1) - just the current row and column indices.

A 1x1 matrix; a target smaller than every element or larger than every element; a target equal to a corner value.

Be ready to explain WHY the top-right (or equivalently, bottom-left) corner is the correct starting point - starting from the top-left or bottom-right corner wouldn't work, since BOTH directions from those corners would move in the SAME (increasing or decreasing) direction, not one of each.