CODEWITHSUNDEEP
algorithmmathmatrix
jaya
jaya

Reputation: 355

Which row has the most 1s in a 0-1 matrix with all 1s "on the left"?

Problem

Each row of an n x n matrix consists of 1's and 0's such that in any row, all 1's come before any 0's. Find row containing most no of 1's in O(n).

Example

1 1 1 1 1 0  <- Contains maximum number of 1s, return index 1
1 1 1 0 0 0
1 0 0 0 0 0
1 1 1 1 0 0
1 1 1 1 0 0
1 1 0 0 0 0

I found this question in my algorithms book. The best I could do took O(n logn) time. How to do this in O(n)?

Upvotes: 28

Views: 8356

Answers (5)

Neelabh Singh
Neelabh Singh

Reputation: 2678

int [] getMax1withRow(int [][] matrix){
    int [] result=new int[2];
    int rows=matrix.length;
    int cols=matrix[0].length;
    int i=0, j=0;
    int max_row=0;// This will show row with maximum 1. Intialing pointing to 0th row.
    int max_one=0;// max one
    while(i< rows){
        while(matrix[i][j]==1){
            j++;
        }
        if(j==n){
             result[0]=n;
             result[1]=i;
             return result;
        }
        if(j>max_one){
             max_one=j;
             max_row=i;
        }
        j=0;// Again start from the first column
        i++;// increase row number
    }
    result[0]=max_one;
    result[1]=max_row;
    return result;
}

Time complexity => O(row+col), In worse case If every row has n-1 one except last row which have n 1s then we have be travel till last row.

Upvotes: 0

Rumple Stiltskin
Rumple Stiltskin

Reputation: 10425

Some C code to do this. 

int n = 6;
int maxones = 0, maxrow = -1, row = 0, col = 0;
while(row < n) {
    while(col < n && matrix[row][col] == 1) col++;
    if(col == n) return row;
    if(col > maxones){
        maxrow = row;
        maxones = col;
    }
    row++;
}

Upvotes: 0

codaddict
codaddict

Reputation: 455380

You can do it in O(N) as follows:

Start at A[i][j] with i=j=0.

          1, keep moving to the right by doing j++
A[i][j] = 
          0, move down to the next row by doing i++

When you reach the last row or the last column, the value of j will be the answer.

Pseudo code:

Let R be number of rows
Let C be number of columns

Let i = 0
Let j = 0   
Let max1Row = 0

while ( i<R && j<C )
   if ( matrix[i][j] == 1 )
      j++
      max1Row = i
   else
      i++
end-while


print "Max 1's = j"
print "Row number with max 1's = max1Row"

Upvotes: 13

Prasoon Saurav
Prasoon Saurav

Reputation: 92894

Start with the first row. Keep the row R that has the most numbers of 1s and the index i of the last 1 of R. in each iteration compare the current row with the row R on the index i. if the current row has a 0 on position i, the row R is still the answer. Otherwise, return the index of the current row. Now we just have to find the last 1 of the current row. Iterate from index i up to the last 1 of the current row, set R to this row and i to this new index.

              i
              |  
              v 
R->   1 1 1 1 1 0  
|
v     1 1 1 0 0 0 (Compare ith index of this row)
      1 0 0 0 0 0         Repeat
      1 1 1 1 0 0           "
      1 1 1 1 0 0           "
      1 1 0 0 0 0           "

Upvotes: 2

Thom Smith
Thom Smith

Reputation: 14086

Start at 1,1.

If the cell contains 1, you're on the longest row so far; write it down and go right. If the cell contains 0, go down. If the cell is out of bounds, you're done.

Upvotes: 42

Related Questions