Find row with maximum number of 1s in sorted matrix

Problem: You are given a MxN matrix with each row sorted. Matrix is having only 0′s and 1′s. You have to find row wotth maximum number of 1′s.
eg. matrix given:
000111
001111
011111
000011
111111 // row with max number of 1′s

Method 1: Brute force approach
Traverse the matrix row wise and count number of 1′s. If the number of 1′s is greater than max count than store index of row. Return index with max 1′s.
Time Complexity: O(MxN) M is no of rows,N is no of cols.

Method 2: Using binary search(each row is sorted)
We will find occurence of first 1. Total number o 1′s will be total coumns – index of first 1.
Implementation of above approach:

// function which retrun index of 1st one in each row using binary search  
int getFirstOccurence(int arr\[\], int low, int high)  
{  
  if(high >= low)  
  {  
    int mid = (low + high)/2;  
   
    // check if the middle element is first 1  
    if ( arr\[mid-1\] == 0 && arr\[mid\] == 1)  
      return mid;  
    else if (arr\[mid\] == 0)  
      return getFirstOccurence(arr, (mid + 1), high);  
    else  
      return getFirstOccurence(arr, low, (mid -1));  
  }  
  return -1;  
}  
// function which check max 1's row  
int findRowMaxOne(int mat\[m\]\[n\])  
{  
    int max\_row = 0, max = -1;  
    int i, ind, count;  
    for (i = 0; i < m; i++)  
    {  
       ind = getFirstOccurence(mat\[i\], 0, n-1);  
       count = n - ind;  
       if (ind != -1 && count > max)  
       {  
           max = count;  
           max\_row = i;  
       }  
    }  
   
    return max\_row;  
}

Time Complexity: O(mLogn) where m is number of rows and n is number of columns in matrix.

See also