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).