enjoyalgorithms

Find Row With Maximum Number of 1s

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

Key takeaway: An excellent matrix problem to learn time complexity optimisation.

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 basic idea is to iterate through each row and count the number of ones in each row. We also 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 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 pseudocode

rowWithMaxOnes(X, row, col)
    maxOneCount = 0
    maxRowIndex = -1
    // Count the number of ones in each row
    for i from 0 to row - 1
        rowOneCount = 0
        for j from 0 to col - 1
            if X[i][j] == 1
                rowOneCount = rowOneCount + 1
        // Update the row with the most ones found so far
        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 know that each row is sorted. Can we use this information to improve time complexity?

For each row, instead of using linear search, we can apply binary search to find the first instance of 1, where 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.

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

For this, we are using recursive binary search where the base case occurs when l > r.

  • Calculate the mid index i.e. mid = l + (r - l)/2.
  • If value at mid is 1 and 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] == 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 in the left half. So we 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.
  • When recursion reaches the base case, it means we didn't find any 1 in the array. We return -1.

Solution pseudocode

searchFirstOne(X, l, r)
    if l > r
        return -1

    mid = l + (r - l) / 2
    // Check whether mid is the first position containing 1
    if X[mid] == 1 and (mid == 0 or X[mid - 1] == 0)
        return mid
    else if X[mid] == 0
        return searchFirstOne(X, mid + 1, r)
    else
        return searchFirstOne(X, l, mid - 1)

rowWithMaxOnes(X, row, col)
    maxOneCount = 0
    maxRowIndex = -1
    for i from 0 to row - 1
        firstOneIndex = searchFirstOne(X[i], 0, col - 1)
        if firstOneIndex != -1
            rowOneCount = col - firstOneIndex
            if 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? Here are two observations from the 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 the row <= count of 1's in the next row. The same idea applies to all the consecutive rows.

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, update 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.
  • We return the final value of the max row index.

Note: Each time we move left, we have found a row with more 1s than the previous best.

Solution pseudocode

rowWithMaxOnes(X, row, col)
    maxRowIndex = -1
    currCol = col - 1  // Start at the top-right corner
    // Scan each row, moving left while the current value is 1
    for i from 0 to row - 1
        // Move left across 1s, each step finds a row with more 1s
        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 and the time complexity looks O(mn). But this is not 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. In other words: The above idea creates a staircase path (each step either moves left or down). The pointers never move backwards, so the algorithm examines at most m + n entries.

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

Enjoy learning, Enjoy coding, Enjoy algorithms!

More from EnjoyAlgorithms

Self-paced Courses and Blogs