466. Find Row with Maximum Ones in Sorted Binary Matrix

Given an m×n binary matrix where each row is sorted (0s followed by 1s), return the 0-indexed row number that contains the maximum number of 1s. If multiple rows tie, return the one with the smallest index. Solve in O(m log n).

Input: A 2D binary matrix where each row is sorted (0s then 1s).

Output: 0-indexed row number with maximum ones (-1 if all zeros).

Examples

Input: [[0,0,1,1],[0,1,1,1],[0,0,0,1],[0,0,0,0]]
Output: 1
Explanation: Row 1 has 3 ones (most). Return index 1.

Input: [[1,1,1],[0,1,1],[0,0,1]]
Output: 0
Explanation: Row 0 has all 3 ones.

Input: [[0,0,0],[0,0,0]]
Output: -1
Explanation: All zeros — return -1.

Constraints

• 1 <= m,n <= 10^3
• matrix[i][j] is 0 or 1
• Each row sorted non-decreasing

Asked by