Search a 2D Matrix

mediumBinary Search+20 XPTime limit 2s

Each row of the matrix is sorted, and the first value of every row is greater than the last value of the row above. Decide whether target is in the matrix.

Input:

line 1: r c
next r lines: c integers each
last line: target

Output: true or false.

Constraints: 1 ≤ r, c ≤ 300, −10⁴ ≤ value, target ≤ 10⁴. Aim for O(log(r·c)).

Think about it: read row by row, the matrix is one sorted list of r·c numbers. Binary search over index k and map it to cell (k / c, k % c).

Sample input 1

3 4
1 3 5 7
10 11 16 20
23 30 34 60
3

Sample output 1

true

Sample input 2

3 4
1 3 5 7
10 11 16 20
23 30 34 60
13

Sample output 2

false

📖 Stuck? Learn the pattern

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…