Asked at

Search A 2D Matrix

Medium
VerifiedArrayBinary SearchMatrix~20 min

Each row of matrix is sorted ascending, and the first value of every row is greater than the last value of the row above it. Return whether target is present.

Because the values form one sorted sequence when read row by row, binary search over the flattened index. The input arrives as a single object { matrix, target }.

Examples

in{ matrix: [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target: 3 }
outtrue

3 sits in the first row.

in{ matrix: [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target: 13 }
outfalse

13 is absent from the matrix.

Constraints

  • 1 ≤ rows, cols ≤ 100
  • -10⁴ ≤ matrix[i][j], target ≤ 10⁴
  • Target: O(log(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.