Find in a Row-Chained Grid

Medium

You get an m × n grid of integers grid with this layout: - every row is sorted in non-decreasing order; - the first number of each row is greater than the last number of the row above. In other words, writing the rows out one after another gives a sorted list. Return True if value appears in the grid, otherwise False. Aim for O(log(m·n)).

Example 1

grid=[[2, 4, 4, 9], [12, 15, 18, 21], [30, 33, 40, 41]], value=18 → True

18 sits in the second row.

Example 2

grid=[[2, 4, 4, 9], [12, 15, 18, 21], [30, 33, 40, 41]], value=10 → False

10 is above the end of the first row and below the start of the second, so it is nowhere.

Example 3

grid=[[-7]], value=-7 → True

Constraints

1 ≤ m, n ≤ 100
-10⁴ ≤ grid[i][j], value ≤ 10⁴
Rows are sorted in non-decreasing order
grid[i][0] > grid[i-1][n-1]

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search Matrix

Similar problems

Find in a Grid Sorted Both Ways Medium K-th Smallest in a Sorted Grid Medium Route With the Highest Bottleneck Medium A Value Shared by Every Row Medium Largest Light Square Medium

Input

grid=[[2, 4, 4, 9], [12, 15, 18, 21], [30, 33, 40, 41]], value=18

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 134 tests on the server, hidden ones included.