Search a Row-Major Grid
EasyBinary Search
Problem
A seating chart is stored as an m × n grid of seat numbers. Each row is sorted in increasing order, and the first number of every row is larger than the last number of the row above it.
Return true if target is in the grid, in O(log(m · n)) time.
Example 1
- Input:
- grid = [[1, 4, 7], [10, 13, 15], [20, 22, 30]], target = 13
- Output:
- true
Example 2
- Input:
- grid = [[1, 4, 7], [10, 13, 15], [20, 22, 30]], target = 14
- Output:
- false
Example 3
- Input:
- grid = [[5]], target = 5
- Output:
- true
Constraints
- 1 ≤ m, n ≤ 300
- -10^4 ≤ grid[i][j], target ≤ 10^4
- Rows are increasing and each row starts above the end of the previous one.
Hint
Show the first hint
Read the grid row by row. What does the sequence of numbers look like?
Walkthrough
How to approach it
01Clarify before coding
- Does every row start above the previous row's end? Yes; that is what makes the grid one sorted list.
- Are all rows the same length? Yes, n columns.
- Is a boolean enough? Yes.
02Brute force
Check every cell, or binary search each row separately.
Cost: O(m · n) for the scan, O(m log n) for per-row searches. Both ignore the ordering between rows.
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.