Last Updated: 19 Dec, 2020
Row with max 1s
Moderate
Asked in companies
You are given a 2D matrix 'ARR' (containing either ‘0’ or ‘1’) of size 'N' x 'M', where each row is in sorted order.
Find the 0-based index of the first row with the maximum number of 1's.
Note :
If two rows have the same number of 1’s, return the row with a lower index.
If no row exists where at-least one '1' is present, return -1.
Example:
Input: ‘N’ = 3, 'M' = 3
'ARR' =
[ [ 1, 1, 1 ],
[ 0, 0, 1 ],
[ 0, 0, 0 ] ]
Output: 0
Explanation: The 0th row of the given matrix has the maximum number of ones.
Input Format :
The first line contains two integers, ‘N’ and ‘M’, representing the number of rows and columns of the 2D matrix.
Each of the next N lines contains M space-separated integers representing the elements of the matrix ARR.
Output Format :
Return the row index, which contains the maximum number of 1’s.
Note :
You do not need to print anything; It has already been taken care of. Just implement the given function.
Approaches
Our intuition is to traverse the given matrix row by row, and keep on counting the number of ‘1’s in each row and compare the count with max. And finally, return the index of the row with the maximum ‘1’s. This is a brute force kind of approach.
Just remember one thing while considering two rows have the same number of 1’s then we need to return the row with a lower index.
In the previous approach, we were iterating through all the elements of the matrix. Do we really need to do that? Think of how we can search for a point where the 1’s starts to appear since all the rows are sorted as given in the question.
Steps to follow towards a better approach :
- Since each row is sorted, we can use Binary Search to count the ‘1’s in each row.
- We find the index of the first instance of ‘1’ in each row which the first time we find a ‘1’ in each row.
- The count of ‘1’s will be equal to the total number of columns minus the index of the first ‘1’.
- And finally, we can return the row index with the maximum count of ‘1’s.
In the previous approach, we were searching in each of the given matrix. Can you think of a case in which we can really skip a row in order to make our approach more optimized?
Steps are as follows :
- Get the index of the leftmost ‘1’ in the first row.
- Do the following for every row after the first row.
- If the element on the left of the previous leftmost ‘1’ is ‘0’, then we will ignore this row.
- Else, move left until a ‘0’ is found.
- Update the leftmost index to this index and “maxIndex” (row index with the maximum number of ones) to be the current row.
- Finally, we can return the “maxIndex”.
Similar problems