Fullest Row in a Sorted Bit Grid
EasyMatrix
Problem
A server rack log is an m × n grid of bits: each row is one server and each 1 marks a busy core. In every row the cores are reported sorted, so all 0s come before all 1s.
Return the index of the row with the most 1s. If several rows tie, return the smallest index. If the grid contains no 1 at all, return -1. Aim for O(m + n) time.
Example 1
- Input:
- grid = [[0, 0, 1, 1], [0, 1, 1, 1], [0, 0, 0, 1], [0, 1, 1, 1]]
- Output:
- 1
Rows 1 and 3 both have three 1s; the smaller index wins.
Example 2
- Input:
- grid = [[0, 0], [0, 0]]
- Output:
- -1
Constraints
- 1 ≤ m, n ≤ 1000
- grid[i][j] is 0 or 1
- Each row is sorted in non-decreasing order.
Hint
Show the first hint
In a sorted row, the number of 1s is determined by where the first 1 is. A row beats the best so far only if its first 1 is further left.
Walkthrough
How to approach it
01Clarify before coding
- Which row wins a tie? The smallest index.
- What if there are no 1s? Return -1.
- Is each row sorted 0s then 1s? Yes, which is what makes the staircase walk valid.
02Brute force
Count the 1s in every row, or binary-search each row for its first 1.
Cost: Counting is O(m · n); per-row binary search is O(m log n).
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.