← Adobe questions

Find the row with the maximum number of 1s

Filed under Adobe · Also reported at HashedIn

Free read 1 of 3

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.

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

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

Solution

O(n) time, O(1) space

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