Skills101
← All coding problems

Search in a Row- and Column-Sorted Matrix

mediumMatrix+20 XPTime limit 2s

Every row of the matrix is sorted left to right and every column is sorted top to bottom (both non-decreasing). Unlike a fully sorted matrix, the last value of a row can be larger than the first value of the next row. Answer q questions: "does the value x appear in the matrix?"

Input:

  • line 1: r c
  • next r lines: c integers each
  • next line: q
  • next q lines: one integer x each

Output: q lines, each true or false.

Constraints: 1 ≤ r, c ≤ 300, 1 ≤ q ≤ 10⁴, −10⁹ ≤ values, x ≤ 10⁹.

Think about it: start at the top-right corner. If the value there is larger than x, the whole column below is too large — move left. If it is smaller, the whole row to the left is too small — move down. Each step discards a row or a column, so a search takes at most r + c steps.

Sample input 1

4 4
1 4 7 11
2 5 8 12
3 6 9 16
10 13 14 17
3
5
15
17

Sample output 1

true
false
true

Sample input 2

1 1
-5
2
-5
5

Sample output 2

true
false

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…

Log in to run and submit your code — it's free.