Asked at
Search A 2D Matrix II
MediumVerifiedArrayTwo PointersMatrix~25 min
Each row and each column of matrix is sorted ascending, but rows do not chain together as in the simpler variant. Return whether target is present.
Start at the top-right corner: move left when the value is too big, down when it is too small. The input arrives as a single object { matrix, target }.
Examples
in{ matrix: [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target: 5 }
outtrue
5 appears in the second row.
in{ matrix: [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target: 20 }
outfalse
20 is absent from the matrix.
Constraints
- 1 ≤ rows, cols ≤ 300
- -10⁹ ≤ matrix[i][j], target ≤ 10⁹
- Target: O(rows + cols) time.
Get help
🔑
Sign in to solve
Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.