To find the row with the maximum number of 1's in a sorted binary matrix, we can take advantage of the fact that each row is already sorted — meaning all the 0s appear before the 1s in each row.
The goal is to determine which row contains the most 1's, and if there’s a tie, return the first such row (i.e., the row with the smallest index).
Understanding Different Scenarios:
- If a row has 0 ones (e.g., [0, 0, 0]), we simply move to the next row.
- If a row has all ones (e.g., [1, 1, 1]), then this row has the maximum possible count of 1's — we can even stop searching further because no row can have more.
- If multiple rows have the same number of 1’s, we return the index of the first row that achieves that maximum.
- If no rows have 1's at all, we return
-1
because there’s no valid answer.
- If the matrix is empty (i.e., has no rows), we also return
-1
.
How Binary Search Helps
Since each row is sorted, we don’t have to scan the entire row to count the number of 1’s. Instead, we can use binary search to quickly find the first occurrence of 1 in each row. Once we know the position of the first 1, we can calculate how many 1’s are present in that row (which is simply m - index_of_first_1
).
By applying this to each row and keeping track of the row that gives the highest count, we can find the answer efficiently. At the end, we return the row index with the maximum 1's.
This method works well even for large matrices because binary search keeps the time complexity low (around O(n log m)
where n
is the number of rows and m
is the number of columns).