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: Usng 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.

Please write if you find anything incorrect or any better approach.

5 Thoughts on “Find row with maximum number of 1s in sorted matrix

  1. How about this, the one that checks the matrix coloumn by coloumn. the first time 1 is found, it returns the row number:

    for(j=0;j<N;j++)
    {
    for(i=0;i<M;i++)
    {
    if(A[i][j]==1)
    {
    printf("%d", i);
    exit;
    }
    }
    }

  2. geek_guy on October 31, 2013 at 10:33 am said:

    We can do this in O(N+M) as well.

    Start from top right corner.
    If you encounter 0 go down.
    If you encounter 1 go right.

    You will end up at the column from which maximum number of 1′s starts.

    Example :

    000111
    001111
    011111
    000011
    111111

    start from (0,5)
    there is 1 so you go right (0,4) (current_answer = M-4-1 = 1 )
    there is 1 so you go right (0,3) (current_answer = M-3-1 = 2 )
    there is 1 so you go right (0,2) (current_answer = M-2-1 = 3 )
    there is 0 so you go down (1,2) (current_answer = M-2-1 = 3 )
    there is 1 so you go right (1,2) (current_answer = M-2-1 = 3 )
    there is 1 so you go right (1,1) (current_answer = M-1-1 = 4 )
    there is 0 so you go down (2,1) (current_answer = M-1-1 = 4 )
    there is 1 so you go right (2,0) (current_answer = M-0-1 = 5 )
    there is 0 so you go down(3,0) (current_answer = M-0-1 = 5 )
    there is 0 so you go down (4,0) (current_answer = M-0-1 = 5 )
    there is 1 so you … opps.. we found a row which has all 1′s. and that’s the answer.
    (current_answer = M-(-1)-1 = 6 )

    Hope this makes sense. :)

    • Sweety on July 26, 2014 at 1:08 am said:

      First of all when a 1 is encountered, you go left not right and how are you taking note of the row index with the max.no of 1′s….??

  3. O(n + m) solution. Suppose n rows & m columns

    ….
    currRow = 0
    currCol = m-1
    maxOneRow = -1;
    while(currRow =0)
    {
    if(arr[row][col] == 1)
    {
    myRow = row;
    col–;
    }
    else
    row–;

    return myRow
    }

  4. // Please add check for mid == 0, other wise it will throw exception.

    public int getFirstOccurenceOne(int[] matrixRow, int low, int high) {

    if (high >= low) {

    int mid = (low+high)/2;

    if ( (mid == 0 || matrixRow[mid-1] == 0) && matrixRow[mid] == 1 ) {
    return mid;
    } else if (matrixRow[mid] == 0) {
    return getFirstOccurenceOne(matrixRow, mid+1, high);
    } else {
    return getFirstOccurenceOne(matrixRow, low, mid-1);
    }
    }

    return -1;
    }

Leave a Reply to code Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation