Find the row with maximum number of 1s
Filed under Arcesium · Also reported at Quantiphi
Free read 3 of 3Confirm matrix dimensions and behavior when rows contain only 0s or only 1s.
The question
Given a boolean 2D array of size N x M where each row is sorted in non-decreasing order, find the 0-indexed row number that contains the maximum number of 1s. If multiple rows have the same maximum, return the lowest row index.
Constraints
- Matrix dimensions N and M are between 1 and 1000.
- Each row is sorted independently.
- Time complexity should be better than O(N log M).
Examples
- Input
- mat = [[0, 0, 1, 1], [0, 1, 1, 1], [0, 0, 0, 1], [0, 1, 1, 1]]
- Output
- 1
- Why
- Row 1 and Row 3 have three 1s, but Row 1 has the lower index.
Approach
Confirm matrix dimensions and behavior when rows contain only 0s or only 1s.
Iterate through every element or use binary search on each row to count 1s, resulting in O(N log M) time.
Start at the top-right corner of the matrix. If the element is 1, move left and record the row index. If the element is 0, move down. This achieves O(N + M) time complexity.
Handle matrices with all 0s, all 1s, or a single row/column.
Solution
O(N + M) time, O(1) space
class Solution:
def rowWithMax1s(self, mat):
n, m = len(mat), len(mat[0])
row, col = 0, m - 1
max_row = -1
while row < n and col >= 0:
if mat[row][col] == 1:
max_row = row
col -= 1
else:
row += 1
return max_row
Tips
- What they are testing: Tests ability to optimize from a naive O(N log M) binary search per row to an optimal O(N + M) staircase traversal.
- Common mistake: Performing binary search on every single row instead of utilizing the sorted property across columns to start from the top-right corner.
Follow-ups
- Optimize from MlogN to O(m+n) approach
Related Arcesium questions
Collected from public candidate posts and coding forums. Updated Nov 2026.