Find row with maximum 1's

Easy

Binary search each row for its first 1

Problem

Given a binary matrix where every row is sorted (all 0s then all 1s), return the index of the row containing the most 1s. If several rows tie, return the smallest index.

In simple words

Each row is sorted, so find where its 1s begin; the row starting earliest has the most.

The idea

Each row is sorted with all zeros then all ones, so the index of the first 1 determines how many ones the row has. One binary search per row gives O(rows · log cols), well under scanning every cell.

The trick

Ones in a row = cols - indexOfFirstOne.
A staircase walk from the top-right does it in O(rows + cols).

←→stepspaceplay

1/5

Brute force

timeO(m·n)spaceO(1)

Count each row.

1for (let r = 0; r < R; r++) {2  const ones = mat[r].reduce((s, v) => s + v, 0);3  if (ones > best) { best = ones; bestRow = r; }4}

Input

grid: 3 × 3

Memory

cells marked: 0

Output

best row: —
ones: —
answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: matrix = [[0,0,1],[0,1,1],[0,0,0]]
Output:: 1
Explanation:: Row 1 has the most 1s.

Example 2

Input:: matrix = [[1,1],[0,1]]
Output:: 0
Explanation:: Row 0 is all ones.

Example 3

Input:: matrix = [[0,0],[0,0]]
Output:: 0
Explanation:: No ones anywhere → row 0.

Constraints

1 <= n, m <= 10^3
mat[i][j] is 0 or 1
Each row is sorted.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.