Row with max 1s

Moderate
0/80
Average time to solve is 20m
96 upvotes
Asked in companies
Expedia GroupOYOMicrosoft

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
3 3
1  1  1
0  0  1
0  0  0
Sample Output 1 :
0
Explanation of Input 1 :
The 0th row of the given matrix has the maximum number of ones.
Sample Input 2:
2 2
1  1
1  1
Sample Output 2:
0
Explaination of Sample Output 2:
The 0th and 1st rows of the given matrix have the maximum number of ones, so we will output the lower index value.
Sample Input 3 :
2 1
0
0
Sample Output 3 :
-1
Explaination of Sample Output 3:
No row is present where at-least one '1' is present. Hence the answer is -1.
Constraints :
1 ≤ N, M ≤ 100
0 ≤ ARR[i][j] ≤ 1

Where ARR[i][j] denotes the matrix elements.

Time Limit: 1 sec
Hint

Try to think about how you can count the number of 1’s in each row.

Approaches (3)
Brute Force

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.

Time Complexity

O(N*M), where ‘N’ is the number of rows and ‘M’ is the number of columns in the given matrix.

We traverse through the matrix row-wise which will take ‘N’ iterations and for each row of size ‘M’ will take O(M) complexity to traverse the row, so the overall time complexity will be O(N*M).

Space Complexity

O(1) 

Since no extra space is required, so the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Row with max 1s
Full screen
Console