39. Find the Row With Maximum Number of 1s

Given an r x c binary matrix where every row's 1s are sorted after its 0s (each row is non-decreasing), find the 0-indexed row that contains the most 1s. If there's a tie, print the smallest such row index. If every row has zero 1s, print -1.

Input: The first line contains r and c, the matrix dimensions. The next r lines each contain c space-separated binary values (0 or 1), with each row's 1s sorted after its 0s. Output: Print a single integer - the 0-indexed row containing the most 1s, or -1 if every row is all zeros.

1 <= r, c <= 1000

The special case of a row with ZERO 1s (all zeros) needs to be handled correctly - such a row contributes a count of 0 and should never accidentally be reported as the 'best' row unless every row is entirely empty of 1s.

In a grid of 0s and 1s where each row's 1s always come after its 0s, find which row has the MOST 1s. Brute force: Scan every single cell of every row directly, counting 1s as you go - this costs O(r * c), correct but doesn't take advantage of each row already being sorted. Optimised: Because each row is already sorted (0s then 1s), binary search can find the FIRST 1 in each row in O(log c) time instead of a linear O(c) scan - across all rows, this reduces the total work from O(r * c) down to O(r * log c).

For every row, scan all c cells left to right and count how many are 1 (equivalently, find the first 1 and count to the end, since each row's 1s are grouped after its 0s). Keep track of the row with the highest count seen so far, only updating on a strictly greater count so ties resolve to the smallest index. Checking every cell of every row directly gives time proportional to the full matrix size. Time: O(r*c) Space: O(1)

Start at the top-right corner of the matrix. If the current cell is 1, this row has at least one more 1 than any row explored so far in this column, so record this row as the current best and move one column left to look for more 1s in the same row. If the current cell is 0, this row cannot beat the current best from this column onward, so move one row down instead. Because the pointer only ever moves left or down, the whole matrix is traversed in a single staircase path. Time: O(r + c) Space: O(1)

Since every row is individually sorted with 0s before 1s, binary search each row for the index of its first 1; the count of 1s in that row is simply c minus that index. Doing this per row turns each row's linear scan into a logarithmic search, and comparing the resulting counts across all rows, keeping the first row that ties the current best, finds the answer. Time: O(r log c) Space: O(1)

1. Since each row is sorted (0s then 1s), the count of 1s in a row equals (row length minus the position of the FIRST 1 in that row). 2. For each row, instead of scanning left to right to find the first 1, use binary search to find it faster, since the row is sorted. 3. Track which row has the highest resulting count of 1s, breaking ties by preferring the smaller row index.

Time: O(r log c) - binary search per row, across all rows. Space: O(1) - just a couple of tracking variables for the best row found so far.

every row containing zero 1s (print -1); multiple rows tied for the maximum count (print the smallest such index, per the stated rule); and r = c = 1000 (largest, confirming a per-row binary search beats a linear scan).

Be ready to explain precisely how binary search finds 'the first 1' in a sorted 0s-then-1s row (essentially searching for the boundary between the two groups) - this exact 'find the boundary' binary search pattern reappears in many other problems.