Last Updated: 29 Jan, 2021

Row with Maximum 1's

Easy

Asked in companies

Solve now

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).

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

Solve now

Approaches

01 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’.

Solve now

02 Approach

The main observation here is that each row is already sorted in increasing order. Hence we can apply binary search in each row to find the number of ones each row has.

Here is the algorithm:

We initialise two integer variables ‘maxOnes’ and ‘rowIndex’ to 0, representing the maximum number of ones found till now and index of that row, respectively.
Now we will do the following for every row:
1. Count the number of ones using binary search.
2. If ‘currOnes’ is greater than ‘maxOnes’, update ‘maxOnes’ and ‘rowIndex’.
Finally, return ‘rowIndex’.

Solve now

03 Approach

The main observation here is that instead of doing binary search in every row, we first check whether the row has more 1s than max so far. If the row has more 1s, then move until a zero is found.

Here is the algorithm:

Get the index of rightmost 0 in the first row.
Now do the following for every row after the first row:
1. If the element on the previous rightmost 0 is 0, ignore this row.
2. Else move left until a 0 is found. Update the rightmost index to this index and ‘maxRowIndex’ to be the current row.
Finally, return the ‘maxRowIndex’.

Solve now