Row With Max 1s

Difficulty: Medium, Asked-in: Amazon, Microsoft, Paytm

Key takeaway: This is an excellent matrix problem to learn step by step time complexity optimization.

Let’s understand the problem

Given a 2D boolean array of size m x n, where each row is sorted. Write program to find the row with the maximum number of 1s.

Examples

Input: X[][]
0 1 1 1
1 1 1 1 <- row with max number of 1's
0 0 1 1
0 0 0 0

Output: 1 (0-based indexing)

Input: X[][]
0 0 1 1
0 0 0 1 
0 1 1 1 <- row with max number of 1's
0 0 0 1

Output: 2

Discussed solution approaches

Brute force solution using row-wise traversal
Using row-wise binary search
Efficient solution using two nested loops

Brute force solution using row-wise linear search

Solution idea

A straightforward method is to iterate through each row of the array and count the number of ones in each row. We can then keep track of the maximum number of ones seen so far and the index of the row with the maximum number of ones. At the end, we can return the index of the row with the maximum number of ones.

To implement this, we use two nested loops and three variables:

rowOneCount to track the count of 1's in each row.
maxOneCount to track the count of the max number of 1's.
maxRowIndex to track the row-index with max number of 1's.

Solution code C++

int rowWithMaxOnes(int X[][], int row, int col)
{
    int maxOneCount = 0;
    int maxRowIndex = -1;
    for (int i = 0; i < row; i = i + 1)
    {
        int rowOneCount = 0;
        for (int j = 0; j < col; j = j + 1)
        {
            if (X[i][j] == 1)
                rowOneCount = rowOneCount + 1;
        }
        if (rowOneCount > maxOneCount)
        {
            maxOneCount = rowOneCount;
            maxRowIndex = i;
        }
    }
    return maxRowIndex;
}

Solution code Python

def rowWithMaxOnes(X, row, col):
    maxOneCount = 0
    maxRowIndex = -1
    for i in range(row):
        rowOneCount = 0
        for j in range(col):
            if X[i][j] == 1:
                rowOneCount = rowOneCount + 1
        if rowOneCount > maxOneCount:
            maxOneCount = rowOneCount
            maxRowIndex = i
    return maxRowIndex

Time and space complexity analysis

We are traversing each matrix element using nested loops and doing O(1) operation at each iteration. So time Complexity = n*m*O(1) = O(nm). We are using constant extra variables, so space complexity = O(1).

Using binary search

Solution idea

We already know that each row is sorted. Can we use this information to improve the time complexity? Let's think!

For each row, instead of using linear search, we can apply binary search to find the first instance of 1, where the binary search will return the index of the first occurrence.
Now we can easily calculate the number of 1s in the row, which is equal to the total number of columns minus the index of the first 1.
During this process, we also update the count of the max number of 1s and row index with max 1's.

Solution steps

We declare four variables to track the count of 1's in a row(rowOneCount), overall max count of 1's (maxOneCount), index of the first occurrence of 1 (firstOneIndex), and row-index with max number of 1's (maxRowIndex). For accessing each row, we run a loop from i = 0 to row - 1:

For each row i, we start by searching the first occurrence of 1 using the binary search i.e. firstOneIndex = searchFirstOne(X[], 0, col - 1). We are passing 0 as the left parameter and col -1 as the right parameter because the total number of elements in each row is equal to the total number of columns.
Now we calculate the total number of 1's in each row i.e rowOneCount = col - firstOneIndex
if(firstOneIndex != -1 && rowOneCount > maxOneCount), we update the value of maxOneCount with rowOneCount and maxRowIndex with i.
```
if (firstOneIndex != -1 && rowOneCount > maxOneCount) 
{ 
  maxOneCount = rowOneCount
  maxRowIndex = i 
} 
```
By end of the loop, we return the value stored in maxRowIndex.

Searching the first occurrence of 1: searchFirstOne(X[], l, r)

As mentioned above, we can apply the binary search to find the first occurrence of the one. For this, we are using recursive binary search where the base case occurs when l > r. So if(l <=r), we execute the following steps:

Calculate the middle index i.e. mid = l + (r - l)/2
If the value at mid is 1 and the previous value at mid - 1 is 0, it means, the first 1 is present at the mid index. There is another corner case when the first one is present at the first position: if mid = 0 and X[mid] == 1. In both situations, we return mid-index as the first occurrence.
```
if ((X[mid - 1] == 0 || mid == 0) && X[mid] == 1) 
  return mid
```
If(X[mid] == 0), all the left half values will be zero, and the first 1 may be present somewhere in the right half. So we search the occurrence of the first 1 in the right half using the same function recursively with mid + 1 and r as the left and right end.
Otherwise, if both the above conditions are false, then the mid index is at some 1, not the first occurrence. In other words, the first one will be present somewhere in the left half. So we need to search the occurrence of the first 1 in the left half using the same function recursively with l and mid - 1 as the left and right end.
```
else if (X[mid] == 0) 
  return searchFirstOne(X, mid + 1, r) 
else
  return searchFirstOne(X, l, mid - 1)
```
When recursion reaches the base case, it means we didn't find any 1 in the array. We return -1.

Solution code C++

// Function to search the first index of 1 in the given row
int searchFirstOne(int X[], int l, int r) 
{ 
    if (l <= r) 
    { 
        int mid = l + (r - l)/2;
        
        if ((X[mid - 1] == 0 || mid == 0) && X[mid] == 1) 
            return mid;
            
        else if (X[mid] == 0) 
            return searchFirstOne(X, mid + 1, r); 
        else
            return searchFirstOne(X, l, mid - 1); 
    } 
    return -1;
} 

// Function to find the row with maximum number of 1s
int rowWithMaxOnes(int X[][], int row, int col)
{ 
    int maxOneCount = 0;
    int maxRowIndex = -1;
    for (int i = 0; i < row; i = i + 1) 
    { 
        int firstOneIndex = searchFirstOne(X[i], 0, col-1);
        int rowOneCount = col - firstOneIndex;
        if (firstOneIndex != -1 && rowOneCount > maxOneCount) 
        { 
            maxOneCount = rowOneCount;
            maxRowIndex = i;
        } 
    } 
    return maxRowIndex;
}

Solution code Python

def searchFirstOne(X, l, r):
    if l <= r:
        mid = l + (r - l) // 2
        if (X[mid - 1] == 0 or mid == 0) and X[mid] == 1:
            return mid
        elif X[mid] == 0:
            return searchFirstOne(X, mid + 1, r)
        else:
            return searchFirstOne(X, l, mid - 1)
    return -1

def rowWithMaxOnes(X, row, col):
    maxOneCount = 0
    maxRowIndex = -1
    for i in range(row):
        firstOneIndex = searchFirstOne(X[i], 0, col - 1)
        rowOneCount = col - firstOneIndex
        if firstOneIndex != -1 and rowOneCount > maxOneCount:
            maxOneCount = rowOneCount
            maxRowIndex = i
    return maxRowIndex

Time and space complexity analysis

Time complexity = number of rows * time complexity of binary search to find first 1 in each row = n * O(logm) = O(nlogm), where n is the number of rows, and m is the number of columns.

We are using recursive binary search, so space complexity depends on the size of the call stack which is equal to the height of the recursion tree. Space complexity = O(logn) (Think!)

Efficient approach by traversing top-right corner to bottom left corner using nested loops

Solution idea

Can we improve the time complexity further? Think! Here are two observations from the given input matrix: 1) Each row is sorted, so all the 1's in any row will be lined up to the right end. 2) For the first 1 in any row, if there is a 1 in the same column in the next row, then the count of 1's in row <= count of 1's in the next row. The same idea applies to all the consecutive i and i + 1 rows.

So here is an exciting solution idea:

Start from the top-right corner of the matrix and continue moving left until we find 0. During the process, we are updating the value of the max row index.
Now, continue moving downward in that column until we came across 1 in some row i. In this case, all the intermediate rows from 1 to (i-1) have numbers of 1's less than the first row.
Again, in row i, continue moving left until we find 0 and update the value of max row-index.
We will continue the above process until we reach the last row.

Solution steps

We initialize the variable maxRowIndex to track the row index with max 1 and currCol to track the current column.
Now we run a loop from i = 0 to row - 1:
- If(currCol >= 0 && X[i][currCol] == 1), we continue moving left from the top right corner until we find 0. We also keep updating the value of the maxRowIndex.
```
while (currCol >= 0 && X[i][currCol] == 1)
{
    currCol = currCol - 1
    maxRowIndex = i
}
```
- When the above condition is false, we continue moving downward in each column by incrementing the value of i until we came across 1 in some row.
- The above process will continue till i = row.
- By end of the loop, we return the value stored in the maxRowIndex.

Solution code C++

int rowWithMaxOnes(int X[][], int row, int col)
{
    int maxRowIndex = -1;
    int currCol = col - 1;
    for (int i = 0; i < row; i = i + 1)
    {
        while (currCol >= 0 && X[i][currCol] == 1)
        {
            currCol = currCol - 1;
            maxRowIndex = i;
        }
    }
    return maxRowIndex;
}

Solution code Python

def rowWithMaxOnes(X, row, col):
    maxRowIndex = -1
    currCol = col - 1
    for i in range(row):
        while currCol >= 0 and X[i][currCol] == 1:
            currCol = currCol - 1
            maxRowIndex = i
    return maxRowIndex

Time and space complexity analysis

There are two nested loops in the code and the time complexity looks O(mn). But this is not the correct analysis. If we observe closely, we traverse each row and column once, i.e. outer loop traverses each row, and the inner loop traverses each column.

Let's think from another perspective: When we are traversing any row from right to left, then all the columns in that path will be traversed once. Similarly, when we traverse any column from top to down, all the rows in that path will be traversed once.

So total loop iteration = Total number of rows + Total number of columns = m + n. At each loop iteration, we are doing O(1) operation. So time complexity = Total loop iteration * O(1) = (m + n) * O(1) = O(m + n).

We are using a constant number of variables, so space complexity = O(1)

Critical ideas to think!

What is the worst and best case scenario of the efficient approach?
Why are we starting from the top right corner? can we solve the problem from a different starting point?
Can we implement the 2nd solution using the iterative binary search?
Why are we moving in the same row if the current cell has a value of 1?

Comparisons of time and space complexities

Using row-wise traversal: Time = O(nm), Space = O(1)
Using binary search: Time = O(nlogm), Space = O(logn)
Using nested loops: Time = O(m + n), Space = O(1)

Matrix-based problems to practice

Search in a 2D matrix
Rotate a matrix by 90 degrees in an anti-clockwise direction
Transpose of a matrix
Set matrix zeroes
01 Matrix
Reshape the matrix
Toeplitz matrix

Enjoy learning, Enjoy coding, Enjoy algorithms!

Find Row With Maximum Number of 1s

Let’s understand the problem

Examples

Discussed solution approaches

Brute force solution using row-wise linear search

Solution idea

Solution code C++

Solution code Python

Time and space complexity analysis

Using binary search

Solution idea

Solution steps

Solution code C++

Solution code Python

Time and space complexity analysis

Efficient approach by traversing top-right corner to bottom left corner using nested loops

Solution idea

Solution steps

Solution code C++

Solution code Python

Time and space complexity analysis

Critical ideas to think!

Comparisons of time and space complexities

Matrix-based problems to practice

More from EnjoyAlgorithms

Self-paced Courses and Blogs