Python Program to Find Row with Maximum number of 1s

In this tutorial, we will write a Python program to find the maximum number of 1s in the given 2D matrix. In the given matrix, each row is sorted we need to get the row that consists of a maximum number of 1s. Let's see the following example.

Example -

Input matrix :

Output:

2

Explanation -

The second row consists of maximum number of 1s.

Let's solve this problem.

Solution

A simple approach is to traverse each row in the given matrix and count the number of 1s and compare with max. Once we get the maximum number of 1s, return that index. We will solve this problem using the binary search algorithm. Let's understand the following example.

Example -

Output:

Index of row with maximum 1s is: 2

Explanation -

In the above code, first we define the find_first_one() function which is a recursive binary search algorithm. It takes in a sorted boolean array (arr), along with the low and high indices defining the search range. It recursively searches for the index of the first occurrence of 1 in the array using a divide-and-conquer approach. If a 1 is found, it returns the index; otherwise, it continues the search on the appropriate side of the array.

Then, the find_row_with_max_ones() function iterates over each row of the given matrix. For each row, it calls the find_first_one() function to find the index of the first occurrence of 1 in that row. It keeps track of the row index (max_row_index) that has the maximum number of ones so far and the count of ones in that row (max_count). If a row has more ones than the previously found maximum, it updates the max_row_index and max_count accordingly. In the end, the find_row_with_max_ones function returns the max_row_index, which represents the index of the row with the maximum number of ones in the given binary matrix.

The time complexity of the above code is 0(m*n) where m is a number of rows and n in a number of columns in a matrix.

Method - 2:

We can optimize the above code further. Instead of doing a binary search in a row, we first check whether the row has more 1s than max so far. If row consists of more 1s, the only count 1s in the row. We don't need to implement the binary search in a complete row to find the 1s in a row. We do a search before the index of the last max.

Let's understand the following example.

Example -

Output:

Index of row with maximum 1s is: 2

Explanation -

The find_first_one() method works same as we have explained previous code. The find_row_with_max_ones() function takes the matrix as an input and return the index of the row with the maximum number of ones. We define the max_ones with the index of the first one in the first row of the matrix and also initialize max_row_index as 0 and max_count as -1. Then it iterates over the renaming rows of the matrix and it performs the following checks.

1. It checks if max_ones is not -1 (indicating a one has been found previously) and if the element in the column corresponding to num_cols - max_ones - 1 is 1. This is done to ensure that the current row has the potential to have more ones than the previous maximum row.
2. If the conditions are met, it calls the find_first_one function to find the index of the first occurrence of one in the remaining portion of the row. It also checks if the number of ones in the row from that index to the end (num_cols - index) is greater than the current maximum count.
3. If the conditions in step 2 are satisfied, it updates max_ones to be the difference between num_cols and index, indicating the number of ones in the row. It also updates max_row_index to be the current row index.
4. If the conditions in step 1 are not met, it resets max_ones by finding the index of the first one in the current row.

Finally, the function returns the value of max_row_index, which represents the index of the row with the maximum number of ones in the given matrix.

The time complexity of the above code is the 0(mlogn) and auxiliary space is 0(logn).

Method - 3:

Let's understand another method.

Example -

Output:

Index of row with maximum 1s is: 2

Explanation -

The function find_row_with_max_ones() takes the matrix as an argument. It determines the number of rows and columns in the matrix using the len() function. It initializes the max_row_index variable to 0, which will store the index of the row with the maximum 1s.

It initializes the index variable to num_cols - 1, which represents the last column index. The function iterates over each row of the matrix using a for loop.

Inside the loop, a flag variable is set to False to indicate whether the current row has more 1s than the previous row.

It then enters a while loop that checks if the index is greater than or equal to 0 and if the element at that index in the current row is 1. If the condition is true, it sets the flag variable to True and decrements the index by 1 to move to the previous column.

Once the while loop ends, it checks if the flag is True, indicating that the current row has more 1s than the previous row. If the flag is True, it updates the max_row_index to the current row index.

After the loop ends, it checks a special case where the maximum row index is 0 and the last element in the first row is 0. If this condition is true, it returns 0. Finally, it returns the max_row_index.

Time Complexity: The time complexity of the above code is O(m+n) where m is the number of rows and n is the number of columns in the matrix.