Matrix: Find a row with maximum number of 1’s in a binary matrix

Problem Statement:

You are given a m*n binary matrix, you need to find a row that has maximum number of 1’s in it. Each row in the matrix is sorted.

Example:

Input matrix
0 0 1 1
0 0 1 1
1 1 1 1 // this row has maximum number of 1s
0 0 0 0

Solution:

This can be solved in 2 different ways.

1. Brute force approach
2. Binary Search approach

1. Brute force approach

In this approach, we traverse the array row by row and then count the number of 1s and display the row with maximum number of 1’s.

This approach will take Time Complexity = O(n*m)

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <queue>

using namespace std;

int row_with_max_1s(int arr[20][20], int r, int c) 
{ 

    int max_1 = 0;
    int max_row_index = -1; 

    ///traverse row wise matrix
    for (int i=0; i<r; i++) 
    { 
      int count_number_of_1 = 0;
      for (int j=0; j<c; j++) 
      {
         if(arr[i][j] == 1)
            count_number_of_1 ++;
      } 

      //if current row has more number of 1s then update the max 1's value and then row index
      if(count_number_of_1 > max_1)
      {
         max_row_index = i;
         max_1 = count_number_of_1;
      }
    } 
  

    return max_row_index; 
}

int main() 
{ 
    int r = 3, c = 3; 
    int m[][20]= { {0,1,1}, {1,1,1}, {0,0,0} }; 
    cout << "Array row with max number of 1s is " << row_with_max_1s(m, r, c) << endl; 
    return 0; 
}

Output:

Array row with max number of 1s is 1

2. Binary Search approach

In this approach, we know that each row is sorted. Hence we can use binary search for each row.

Then we find the index of the first instance of 1, and the total number of columns minus the index of the first 1 will give us the number of 1’s present.

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <queue>

using namespace std;

int get_first_1_in_a_row(int arr[], int low, int high)  
{  
    if(high >= low)  
    {  
        int mid = low + (high - low)/2;  
      
        // Check if the element at middle index is first 1  
        if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)  
            return mid;  
      
        // If the element is 0, move right side  
        else if (arr[mid] == 0)  
            return get_first_1_in_a_row(arr, (mid + 1), high);  
          
        // If element is not first 1, move left side  
        else
            return get_first_1_in_a_row(arr, low, (mid -1));  
    }  
    return -1;  
} 

int row_with_max_1s(int arr[20][20], int r, int c) 
{ 

    int max_1 = 0;
    int max_row_index = -1; 
    int index;

    ///traverse row wise matrix
    for (int i=0; i<r; i++) 
    { 
      index = get_first_1_in_a_row(arr[i], 0, c-1);
      if (index != -1 && c-index > max_1)  
        {  
            max_1 = c - index;  
            max_row_index = i;  
        }  
    }  
  
    return max_row_index;
}

int main() 
{ 
    int r = 3, c = 3; 
    int m[][20]= { {1,0,1}, {1,1,1}, {0,0,0} }; 
    cout << "Array row with max number of 1s is " << row_with_max_1s(m, r, c) << endl; 
    return 0; 
} 

Output:

Array row with max number of 1s is 1