474. Search a 2D Matrix II (Row & Column Sorted)

Given an m×n matrix where each row is sorted left-to-right and each column is sorted top-to-bottom (but rows are NOT necessarily continuous), determine if target exists. Solve in O(m+n).

Input: A 2D integer matrix (sorted by row and column) and integer target.

Output: true if target exists, false otherwise.

Examples

Input: [[1,4,7,11],[2,5,8,12],[3,6,9,16]], 5
Output: true
Explanation: Start top-right: 11>5→left; 7>5→left; 4<5→down; 5==5→true.

Input: [[1,4,7,11],[2,5,8,12],[3,6,9,16]], 10
Output: false
Explanation: Staircase search exhausts the matrix without finding 10.

Input: [[1]], 1
Output: true
Explanation: Single element matches.

Constraints

• m == matrix.length
• n == matrix[0].length
• 1 <= m,n <= 300
• -10^9 <= matrix[i][j] <= 10^9
• Each row sorted ascending
• Each column sorted ascending

Asked by