Row with Maximum 1's

Easy

0/40

Average time to solve is 10m

59 upvotes

Asked in companies

Problem statement

You have been given a non-empty grid ‘mat’ with 'n' rows and 'm' columns consisting of only 0s and 1s. All the rows are sorted in ascending order.

Your task is to find the index of the row with the maximum number of ones.

Note: If two rows have the same number of ones, consider the one with a smaller index. If there's no row with at least 1 zero, return -1.

Example:

Input: 'n' = 3, 'm' = 3, 'mat' = [[1, 1, 1], [0, 0, 1], [0, 0, 0]]

Output: 0

Explanation: The row with the maximum number of ones is 0 (0 - indexed).

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first input line contains two space-separated integers, ‘n’ and ‘m’ representing the number of rows and columns of the grid, respectively.

From the second line, the next ‘n’ lines represent the rows of the grid. Every row contains ‘m’ single space-separated integers.

Output Format:

For each test case, print the index of the row with the maximum number of ones.

Print the output of each test case in a separate line.

Note: You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1 <= n <= 50
1 <= m <= 50
0 <= mat[i][j] <= 1

Where ‘n’ is the number of rows and ‘m’ is the number of columns.

Time limit: 1 sec

Sample Input 1:

Sample Output 1:

Explanation of the Sample Input 1:

The row with the maximum number of ones is 0 (0 - indexed).

Sample Input 2:

2 2
1 1
1 1

Sample Output 2:

Explanation of the Sample Input 2:

Both rows have the same number of ones. Therefore, we will pick the row with smaller index.

Hint 1

Hint 2

Hint 3

Naively find the number of ones in each row.

Approaches (3)

Approach 1

Approach 2

Approach 3

Naive Approach

We will traverse each row one by one and count the number of ones of each row in a variable ‘currOnes’. We will be updating the ‘maxOnes’ by ‘currOnes’ if ‘currOnes’ is greater than ‘maxOnes’.

Finally, we return the index of the row corresponding to ‘maxOnes’.

Time Complexity

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

In every case, we are visiting all cells of MAT. Hence, the time complexity is O(N * M).

Space Complexity

O(1), i.e. constant space complexity.

(100% EXP penalty)

Row with Maximum 1's

Console