Prerequisites: Matrix, Binary Search (for efficient solution).
Problem: Find the row with maximum no. of 1’s in a row-wise sorted binary matrix. If there are many such rows, print the first one.
Solution Approach:
We can simply iterate through the matrix keeping track of no. of 1s in each row. Only update the answer when you find a row with larger no. of 1s than that in all previous rows.
An efficient approach would be to use binary search on each row to find no. of 1s in it in O(logM) time instead of O(M) time
Time Complexity: O(N * M) for simple approach, O(N*log(M)) for more efficient approach.
Space Complexity: O(1).