Search a 2D matrix II

Problem Search for target in an m x n matrix where rows are sorted left→right and columns top→bottom.

Input / Output

• Input: matrix, target. Output: boolean (or position).

Constraints

• m, n up to 300; O(m+n) expected.

Example

• [[1,4,7,11],[2,5,8,12],[3,6,9,16],[10,13,14,17]], target 5 → true; target 20 → false.

Expected approach

• Staircase from top-right: greater → step left, smaller → step down, equal → found; each comparison discards a row or column → O(m+n), O(1) space. Note this matrix is NOT fully sorted row-major (unlike Search a 2D Matrix I, where one binary search over the flattened array works) — distinguishing the two variants is a common probe. Divide-and-conquer quadrant elimination is a valid but slower-constant alternative.