← Arcesium questions

Find the row with maximum number of 1s

Filed under Arcesium · Also reported at Quantiphi

Free read 3 of 3

Confirm 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

  1. Confirm matrix dimensions and behavior when rows contain only 0s or only 1s.

Solution

O(N + M) time, O(1) space

Python
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.