Find in a Grid Sorted Both Ways

Medium

You get an m × n grid of integers grid. Numbers never decrease from left to right along each row, nor from top to bottom along each column. The end of one row does not have to be smaller than the start of the next one. Return True if value appears in the grid, otherwise False. Checking every cell one by one is too slow: find something faster.

Example 1

grid=[[1, 5, 9], [3, 6, 12], [8, 10, 14]], value=10 → True

10 is in the last row, second column.

Example 2

grid=[[1, 5, 9], [3, 6, 12], [8, 10, 14]], value=7 → False

The grid has no 7.

Constraints

1 ≤ m, n ≤ 300
-10⁹ ≤ grid[i][j], value ≤ 10⁹
Every row is sorted in non-decreasing order
Every column is sorted in non-decreasing order

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search Divide and Conquer Matrix

Similar problems

Find in a Row-Chained Grid 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=[[1, 5, 9], [3, 6, 12], [8, 10, 14]], value=10

Expected

True

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