Find the row with the maximum number of 1s
Filed under Adobe · Also reported at HashedIn
Free read 1 of 3Start from the top-right corner of the matrix. If the current element is 1, all elements to the left are 1; move left and update the max row. If 0, move down.
The question
Given an n x n binary matrix where each row is sorted (all 1s appear before all 0s), find the index of the row that contains the maximum number of 1s.
Constraints
- Matrix is n x n
- Rows are sorted such that 1s come before 0s
- Time complexity should be better than O(n^2)
Examples
- Input
- [[1, 1, 0], [1, 0, 0], [1, 1, 1]]
- Output
- 2
- Why
- Row 2 has three 1s, which is the maximum.
Approach
Start from the top-right corner of the matrix. If the current element is 1, all elements to the left are 1; move left and update the max row. If 0, move down.
This approach visits each row and column at most once, resulting in O(n) time complexity.
Handle matrices with all 0s or all 1s correctly.
Solution
O(n) time, O(1) space
def rowWithMax1s(matrix):
n = len(matrix)
row, col = 0, n - 1
max_row = -1
while row < n and col >= 0:
if matrix[row][col] == 1:
max_row = row
col -= 1
else:
row += 1
return max_row
Tips
- What they are testing: Test with a matrix where all rows are identical or all rows are empty.
- Common mistake: Scanning every element in every row, resulting in O(n^2) complexity.
Related Adobe questions
Collected from public candidate posts and coding forums. Updated Nov 2026.