Search a Row-wise and Column-wise Sorted Matrix

Problem Given a matrix sorted ascending row-wise AND column-wise, search for a target; return its indices (as required by the format) or "Not Found".

Input / Output

• Input: int matrix m x n, target. Output: position or "Not Found".

Constraints

• m, n up to 10^3; O(m + n) staircase expected — beats per-row binary search O(m log n) in the worst case and certainly the O(m*n) scan.

Example

• [[1,4,7],[2,5,8],[3,6,9]], target 6 → (2,1).

Expected approach

• Staircase search from the top-right (or bottom-left): current > target → move left (whole column below is larger); current < target → move down (whole row to the left is smaller); equal → found. Each step eliminates a full row or column → O(m+n), O(1) space. Explain why the two middle corners work and top-left/bottom-right don't (both neighbors move the value the same direction). Duplicate targets and empty matrix are the edge probes.