Country: India

Comment hidden because of low score. Click to expand.
12
of 14 vote

It can be done in O(n) time.
Start from top right element check if its 0 or 1, if its 0 move to j-1 element in that row and store the index of row in a variable,if its 1 move to next row by incrementing i but keeping j same. do the same step here as well.
At the end the variable will consist of row with max 0's.

Comment hidden because of low score. Click to expand.
0

ACRush dude a lil confusion dere..please give a psuedocode..!!

Comment hidden because of low score. Click to expand.
0

Well got it..!! perfect soln..!! :)

Comment hidden because of low score. Click to expand.
0

ACRush dude
First thing ... we need to find row with max no of 1's not 0.
Second thing....It is not of O(n). The worst case will be O(n2).

Comment hidden because of low score. Click to expand.
0

@volvo if we have to find max 1's we can start with top left and move forward to next column in a row if we are getting 1's else if it's a 0 we move down in next row same column.

Since in worst case we traverse n + n = 2n cells of the matrix hence complexity is O(2n) => O(n)

Comment hidden because of low score. Click to expand.
0

ACRush, with the revisions in his latest comment, is correct. It is O(n).

I seem to vaguely recall seeing ACRush on the Google Code Jam scoreboard, if memory serves me right :)

Comment hidden because of low score. Click to expand.
0

ACRush is a chinese Red Coder (world 2nt best coder)... after Petr...

Comment hidden because of low score. Click to expand.
0

Not exactly 2nd best coder... Tourist would come before him and if the problem is way too tough....Then Lyrically is the best amongst all of them...!!!

Comment hidden because of low score. Click to expand.
0

Jesus Christ, that was an awesome algorithm! Of course it finds out the row with maximum number of zeroes, but you get the idea, for maximum number of one's, you just have to start from top-left and go rightwards. Vintage ACRush!

Comment hidden because of low score. Click to expand.
0

Thank you :)

Comment hidden because of low score. Click to expand.
0

I doubt that ACRush will come on career up to comment on this stupid question. He has got a lot work todo.

Comment hidden because of low score. Click to expand.
5
of 5 vote

lets say we have a matrix of size (rows * columns)
scan towards the left on the first row from top right till you hit the last 1.
move downwards on that column till you hit another row with 1
repeat the same

``````// add checks to validate rows and columns > 0
c=columns
r=0
bestr = 0
// start from top right
while (r < rows && c > 0) {
if (a[r][c-1] == 0) r++ else { c--; bestr=r}
}``````

Comment hidden because of low score. Click to expand.
0

This seems like the best answer so far, very simple and worse case is O(m + n).

Comment hidden because of low score. Click to expand.
0

ya. I agree. During interview we settled on this as the best approach worst case is 0(m+n)

Comment hidden because of low score. Click to expand.
0

In your question you have said all rows are sorted.

But I think in this solution you are assuming all rows and columns are sorted.

Comment hidden because of low score. Click to expand.
0

ok i may be understanding the solution in a different way. But the question has ONLY rows sorted(ie, values in rows are sorted).
Ex matrix (4 rows, 3 colmuns):
011 <= 1st row sorted so 1s are at end
001 <= 2nd row sorted
000 <= 3rd row, all 0s
011 <=4th row with 1s at end

Comment hidden because of low score. Click to expand.
0

O(m+n) is not possible with the question that you have stated here.
we need to look into each row, we can apply binary search on column of that row so total time complexity is O(mLogn)

Comment hidden because of low score. Click to expand.
0

00001
00011
00111
00000
11111
your method will just return 00111, so its wrong

Comment hidden because of low score. Click to expand.
0

Questions states that each row is sorted in descending order, so the matrix above should have been this instead:
10000
11000
11100
00000
11111

Having said that, we are asked to find the maximum number of 1s (unless the question was asking for 0s originally). So once we find the last 1 in the first row and start moving downwards, if we encounter another 1 again, why would you want to move left again? Shouldn't you move right instead?

Comment hidden because of low score. Click to expand.
1
of 5 vote

for(int col = n-1 ; col >= 0 ; col --){
for(int row = 0 ; row < n ; row ++ ){
( mat[row][col] == 1 )
return row ;
}

Comment hidden because of low score. Click to expand.
1
of 5 vote

O(log n) time. Start from the middle column (n/2) and check if any row has 1's. If yes, store the column value and proceed in columns with (n/2) to (n) and check only for rows which had 1's previously.

Comment hidden because of low score. Click to expand.
0

Modified Binary Search is perfect solution for this problem.
Ravenclaw don't go from column to column. In next loop also check for ((n/2)+n)/2 column.

Comment hidden because of low score. Click to expand.
0

Ravenclaw dont you think it is O(nlog n) rather than O(log n) coz for iterating all the rows in a column 'n' iterations would be needed?

Comment hidden because of low score. Click to expand.
0

this is O(nlgn) as in worst case consider matrix is full of 1's an no 0.Then for each iteration you check all rows ie n for 1's, as total no of iterations is lg n time complexity amounts to nlgn

Comment hidden because of low score. Click to expand.
0

nimitz and hacker are correct.

Comment hidden because of low score. Click to expand.
1
of 1 vote

At max 2n operation.

``````#include <stdio.h>
#define SIZE 6
int matrix[SIZE][SIZE] = {
{1,1,1,1,0,0},
{0,0,0,0,0,0},
{1,0,0,0,0,0},
{1,1,1,0,0,0},
{1,1,1,0,0,0},
{1,1,0,0,0,0}
};

int main () {
int i=0, j=0;
while ( i < SIZE ) {
if ( j == SIZE )
break ;
while ( j < SIZE ) {
if ( matrix[i][j] == 1 ) {
j ++ ;
}
else break ;
}
i ++ ;
}
printf ( "\n%d", j ) ;
return 0;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

This comment has been deleted.

Comment hidden because of low score. Click to expand.
0

Let's say n/2 coloumn has all 1 , OR even if some of those has 1 in it then ?
ok i am figuring out something here but not clear.
Please elaborate, with the help of interviewer I could find out a solution with 0(m+n), but i think anything with binary search would still be better.

Comment hidden because of low score. Click to expand.
0

Binary search is the right way, matrix is not sorted row wise as you can check the question
011
111
000

sorted column wise --->
but not row wise
|
|
v

so we need to count no of 1's in first row using binary search and keep track of row number and 1's count, then move to the next row and perform the same, at the end you will have 1's count for all the rows, print all the rows which has max 1's which should be closer or equal to n (column length)

Comment hidden because of low score. Click to expand.
0

U r consideration rows for column and column as row !!

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````Mat[n][n]

int row = 0;
int i;
for (i = n- 1; (i >= 0) && (!Mat[i]); --i);

int column = i;

if (i == n - 1)
return row;

int tryingColumn = i + 1;
for (j = 1; j < n; ++j)
{
if (Mat[j][tryingColumn])
{
++tryingColumn;
while (tryingColumn < n)
{
if (Mat[j][tryingColumn])
++tryingColumn;
}
row = j;

if (tryingColumn == n)
return row;
}

}
return row;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````Mat[n][n]

int row = 0;
int i;
for (i = n- 1; (i >= 0) && (!Mat[i]); --i);

int column = i;

if (i == n - 1)
return row;

int tryingColumn = i + 1;
for (j = 1; j < n; ++j)
{
if (Mat[j][tryingColumn])
{
++tryingColumn;
while (tryingColumn < n)
{
if (Mat[j][tryingColumn])
++tryingColumn;
}
row = j;

if (tryingColumn == n)
return row;
}

}
return row;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be done in logn..Keep binary searching on each row till you are encountering one..Remove those rows which got zero..Last row left is the solution..

Comment hidden because of low score. Click to expand.
0

Sounds like NlogN time, not logN. Huge difference.

Comment hidden because of low score. Click to expand.
0
of 0 vote

nice questio though taking the help of binary search it will still be O(nlogn) worst case

1. using binary search find the 1(index i) which has 0 at index i + 1. Once you got that move to 2. next row and check if newRow(index) == 0 then move to next row // this has less 1st than earlier row
3. else apply binarySearch on newRow from index to nth index as shown in step 1 // this has more or equal 1s than earlier row

eventually you will find the row which has max number of 1s

Though worst case it will be O(NlogN)
worst case is

row1 has one 1
row2 has two 1
row3 has three 1.

eventually it will go to complexity o(n logn)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//O(n) time, O(1) space solution. Just move right (while we have 1s) and down. Keep a track of longest row

public int getLongestRowIdx(int[][] m) {
int longestRowIdx = 0;
int longestClmnIdx = 0;
int i = 0;
int j = 0;

for (int i = 0; i < m.length; i++) {
while (j < m.length && m[i][j] == 1)
j++;

if (j - 1 > longestClmnIdx) {
longestRowIdx = i;
longestClmnIdx = j - 1;
}
}

return longestRowIdx;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

int FindMaxRow(int a[][],n)
{
int j = n-1;
int i = 0;
int Max = i;
while( i<n && j<n)
{
if(a[j--] != 0)
{
i++;
j++;
}
if(a[i][j] != 1)
{
i++;
}
else
{
Max = i;
j++;
}
}
Return Max;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

int FindMaxRow(int a[][],n)
{
int j = n-1;
int i = 0;
int Max = i;
while( i<n && j<n)
{
if(a[j] != 0)
{
j--;
}
else
{
i++;
j++;
}
if(i>0)
{
if(a[i][j] != 1)
{
i++;
}
else
{
Max = i;
j++;
}
}
}
Return Max;
}

Comment hidden because of low score. Click to expand.
0

Little correction

int FindMaxRow(int a[][],n)
{
int j = n-1;
int i = 0;
int Max = i;
while( i<n && j<n)
{
if(a[j] == 0)
{
j--;
}
else
{
i++;
j++;
}
if(i>0)
{
if(a[i][j] != 1)
{
i++;
}
else
{
Max = i;
j++;
}
}
}
Return Max;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Very simple.

Just search the first column.If any row has one in it then it would be the biggest as the whole matrix is sorted as mentioned.

Comment hidden because of low score. Click to expand.
0

ya rite :)
thats wat i answered, but then the worst case compexity is 0(mXn)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class MatrixMax {
public static void main(String[] args) {
int mat[][]=new int;

mat=0;
mat=1;
mat=1;
mat=1;
mat=1;
mat=0;
mat=0;
mat=1;
mat=1;
mat=1;
mat=0;
mat=0;
mat=0;
mat=1;
mat=1;
mat=1;
mat=1;
mat=1;
mat=1;
mat=1;
mat=0;
mat=0;
mat=0;
mat=1;
mat=1;

//this is for worst case scenario.. all are zero
/*for(int i=0;i<mat.length;i++){
for(int j=0;j<mat[i].length;j++){
mat[i][j]=0;
}
}*/

int st=0;
int end=mat.length;
int j=0;
int bestr = 0;
int count=0;
j=(st+end)/2;

System.out.println("here  "+j);

while(j>=0 && j<mat.length){
boolean flag=false;
System.out.println("Value of j  "+j);
for(int i=0;i<mat.length;i++){
count++;
if(mat[i][j]==1){
end=j;
bestr=i;
flag=true;
break;
}

}
if(!flag){
st=j;
}
if(j==0 || j==mat.length-1)
break;
j=(st+end)/2;
}
System.out.println("Best r  "+bestr);
System.out.println("Count "+count);
}

}``````

This code is based on binary search...
Even in worst case scenario count=15. (5*5 matrix)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int max_ones(int mat[N][N])
{
int r = 0, c = 0;
while(r < N) {
if(c < N && mat[r][c] == '1')
++c;
else
++r;
}
return c;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

using binary search for N rows, for example, search starts with N/2 position for each row. The search terminates for the row if current position at this row is 0. For the remaining rows, the search repeat until there is only one row left. Worst case O(NlgN)

Comment hidden because of low score. Click to expand.
0

average case should be O((lgN)^2)

Comment hidden because of low score. Click to expand.
0

for a large N, O((lgN)^2) should be better than O(N)

Comment hidden because of low score. Click to expand.
0

can you please give a pseudocode..??

Comment hidden because of low score. Click to expand.
0

The average case is not less than O(N) because you're still taking one or more actions per row.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

it can be done in o(n)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

you r doin it in o(n2) gtfo from there

Comment hidden because of low score. Click to expand.
-1
of 1 vote

correct nice... ACRush

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Could you give the psuedo code for this ?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.