367. Densest Row
A theatre marks each seat in every row with 0 if it is empty and 1 if it is taken. Customers always fill seats from the right side of a row, so in every row all the 0s come before all the 1s.
Given the grid grid of seats, return the index of the row with the most taken seats. If several rows have the same largest count, return the smallest of their indices. If every seat is empty, return 0. Counting every seat takes O(m * n); using the sorted structure of each row you can count a row's 1s in O(log n).
Example 1
- Input:
- grid = [[0,0,1],[0,1,1],[0,0,0]]
- Output:
- 1
- Explanation:
Row 1 has two taken seats, more than any other row.
Example 2
- Input:
- grid = [[0,1],[0,1]]
- Output:
- 0
- Explanation:
Both rows have one taken seat, so the smaller index, 0, is returned.
Constraints
1 ≤ grid.length, grid[0].length ≤ 1000
grid[i][j] is 0 or 1
In each row, all 0s come before all 1s.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(m log n)
- Space
- O(1)