Row with the maximum number of 1s

Easy

Problem

In a binary matrix whose rows are sorted (all 0s, then all 1s), return the index of the first row with the most 1s, or −1 if the matrix has no 1s.

Example 1

Input:  [[0,1,1,1], [0,0,1,1], [1,1,1,1], [0,0,0,0]]
Output: 2

Also asked as: Find row with maximum no. of 1's

Test cases

Case 1

Input:    [[0,1,1,1],[0,0,1,1],[1,1,1,1],[0,0,0,0]]
Expected: 2

Case 2

Input:    [[0,1],[0,1]]
Expected: 0

Case 3

Input:    [[1,1,1]]
Expected: 0

Case 4

Input:    [[0,0],[0,0]]
Expected: -1

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Staircase from top-right

Time O(R + C)Space O(1)

Each row is sorted (0s then 1s). Move left while the current cell is 1; every time you can, that row has more 1s.

function rowWithMostOnes(m) {
let best = -1, c = m[0].length - 1;
for (let r = 0; r < m.length; r++) {
while (c >= 0 && m[r][c] === 1) { c--; best = r; }
}
return best;
}