Row with the maximum number of 1s
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
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;}