Row with Maximum Ones in Sorted Binary Matrix

Problem Given an n x m binary matrix where every row is sorted (all 0s followed by all 1s), find the index of the row containing the most 1s — without scanning every cell.

Input / Output

• Input: an n x m matrix of 0s and 1s, each row sorted in non-decreasing order.
• Output: the index of the row with the maximum count of 1s; on a tie, return the smallest such index.

Constraints

• Each row is individually sorted — this is the property the solution must exploit.
• Target O(n + m); the O(n*m) full scan and even the O(n log m) per-row binary search are considered suboptimal.
• A matrix of all 0s should return -1 or 0 by convention — clarify with the interviewer.

Example

• [[0,0,1,1],[0,1,1,1],[0,0,0,1]] → row 1 has three 1s → output 1.
• Tricky case: all-zero matrix [[0,0],[0,0]] → no row has any 1s; the staircase walk falls straight through to the bottom.