Find in a Two-Way Sorted Grid
MediumBinary Search
Problem
A heat map is stored as an m × n grid in which every row is sorted in increasing order from left to right and every column is sorted in increasing order from top to bottom. Unlike a row-major grid, a row may start below the end of the row above.
Return true if target appears in the grid.
Example 1
- Input:
- grid = [[2, 6, 9], [4, 7, 13], [8, 12, 20]], target = 12
- Output:
- true
Example 2
- Input:
- grid = [[2, 6, 9], [4, 7, 13], [8, 12, 20]], target = 10
- Output:
- false
10 would sit between 9 and 13 in its row and between 7 and 12 in its column, but no cell holds it.
Example 3
- Input:
- grid = [[3]], target = 3
- Output:
- true
Constraints
- 1 ≤ m, n ≤ 300
- -10^9 ≤ grid[i][j], target ≤ 10^9
- Every row and every column is strictly increasing.
Hint
Show the first hint
Start in a corner where one direction makes values bigger and the other makes them smaller.
Walkthrough
How to approach it
01Clarify before coding
- Is the grid one sorted list when read row by row? No: rows can overlap, so flattening does not work.
- Can the grid have a single row or column? Yes.
- Is a boolean enough? Yes.
02Brute force
Check every cell, or binary search every row.
Cost: O(m · n) for the scan; O(m log n) for per-row binary search, which is fine but not the elegant answer.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.