CareerCup

public int findMaximTrueEls(boolean[][] arr)
{
for(int i=arr.length-1;i>=0;i--)
{
for(int j=0;j<arr[0].length;j++)
{
if(arr[i][j])
{ return i;
}
}
}
return -1;
}

You could also perform binary search on each row if you need to achieve the best average run time.

const int M = 100;
const int N = 100;

int findRow(bool matrix[M][N])
{
int i, j, row;
i = j = row = 0;

while (i < M && j < N)
if (matrix[i][j])
{
row = i; ++j;
} else ++i;

return row;
}

// time complexity is O(M+N)

Hi Loony,

Can you please post an example..

1 1 1 1 0 0 0
1 1 0 0 0 0 0
1 1 1 0 0 0 0
1 1 1 1 1 0 0
in this case should be ans is 3(index 0)???

//Following apporach time complexity is o(n), binary search can be used to further optimize it
//When return -1 means no row has true value
public int maxtrueRow(boolean val[][], int m, int n){
int row = -1, i=0, j=0;
while(i < m && j < n){
if(val[i][j]){
j++;
row = i;
}else{
i++;
}
}
return row;
}

//The worst case time complexity for this approach is O(mlogn), so it suits when m << n
//When return -1 means no row has true value
public int maxtrueRowBS(boolean val[][], int m, int n){
int row = -1, i=0, j=0;
while(i < m && j < n){
//BS finds the first false in row i of val starting col j
//If no false value found, return -1;
int k = BS(val, i, j);
if(k == -1) {row = i; break;}
if(k > j) { j = k; row = i;}
i++;
}
return row;
}

Algo:

Start with the last column.
Add all the elements of the column.

if the summation is == 0, select a column to left.and add all the elements of that column.
repeat above step, till you find a column with summation value > 0.
here you found out how many 1s does the rows with max 1s have.
to find our what is the row number, there one trick we can apply while adding all the elements of the column.
The trick is: value of the 1st row is multiplies by 1.
value of the 2nd row is multiplied by 2.
and so on.

so when we find the summation value > 0, the value of the summation gives us row with the max 1s. (1 based index).

worst case O(M*N)

int maxRow(int arrayOfBool[][cols],int rows,int cols)
{

int i = 0 ,j = 0;

for(j=cols-1;j>=0;j--)
{
for(i=0;i<rows;i++)
{
if(arrayOfBool[i][j])
return (i+1);

}
}

return 0;
}
//worst case tc O(rows*cols) case: array with all zeroes
//best case O(1) // case array[rows-1][cols-1] = 1

int maxRow(int arrayOfBool[][cols],int rows,int cols)
{

int i = 0 ,j = 0;
int maxR = -1;
while(i<rows && j<cols)
{
if(arrayOfBool[i][j])
{
maxR = i;//mar current row as the max row
j++; // go to next col
}
else // if u find zero , go to next row, keep the col num intact
i++; // go to next row
}
return maxR;
}

An array of boolean is stored continguously in memory. Say it's 17 by 10, it uses 170 bits of contiguous data.
I think the proper answer would take into account machine architecture and significantly improve performance by operating with Words (32 bits) rather than individual bits. This strategy is only valid if processing >= on 32 bits one time is faster than on individual bits 32 times. I believe that this is the case.

Therefore, one would need to employ two algorithms. If the number of columns is less than 32, then only algorithm #2 is used. if the number of columns is a multiple of 32, only algorithm #1 is used, and if it's anything else, use #1 for the first x multiples of 32 bits, then use algorithm #2.

An alternative would be to resize the array to the next 32-bit multiple. This may be effective depending on what data you anticipate getting.

Algorithm #1 would be as follows:
1. Compare the first 32 bits of each row moving down one at a time. As soon as you reach a number which is maxInt, move right to the next chunk of 32 bits and continue to compare rows moving down one at a time, moving right whenever you reach maxInt. You stop when you reach the bottom, and your answer is the largest value.

There is no technical change in algorithm performance using big O notation, but in practice it is n/32 + m. Or, way faster. Worst case = algorithm 2, which is the bit-by-bit strategy.

int FindRow( int** Matrix , int R , int C )
{
    int r=0,c=0;
    
    int MaxTrue=0;
    int MaxRow=-1;
    
    while( r<R && c<C )
     {
           if( Matrix[r][c]==1 )
             c++;
           else
             {
                 if( MaxTrue < c ) /* 0 Indexed */
                  {
                      MaxTrue=c;
                      Maxrow=r;
                  }
                     r++ ;  
                     
                     
                     }
                     
                     
                     }
                     
                     
               if( c==C )return r;
                     
                     return MaxRow;
                     
                     }

rows are always sorted 1s on left and 0s on right (means decresing) so you can apply binary search to find index where array element turing 1to0, (logQ) (of PxQ matrix)
you have to do it for every row(P)and find maximum.
this can be done in O(P*logQ), with O(p) space.

we can go column wise
for eg
111000
110000
111100
000000
so in this case if we move column wise then we can get the ans
scan 1st row till 0 is found. term it as max row.jump to 2nd row same column N chk if it is 1 then move righthand side row wise otherwise jump to next row.

Easier way:
Sum elements of each row; and then find the max of it between rows, and return the index; it can be return using just one loop