wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Maximum zeros
        
(Message started by: mad on Mar 8^th, 2008, 5:39pm)

Title: Maximum zeros
Post by mad on Mar 8^th, 2008, 5:39pm

You are given a NXN matrix, each element of which is either 0 or 1 with the restriction that no 0 can appear before a 1 in any row. Example-

1 0 0 0 0
1 1 0 0 0
1 0 0 0 0
0 0 0 0 0
1 1 1 1 1

Assuming the row and col indices to be zero based, you have to return the index of the row with maximum number of zero's.

Achieve:
Space- O(1)
Time- O(n)

I think a similar question has been posted before.
But, that required checking each row making it O(n^2). Can there be an O(n) solution [hide]by say checking the diagonal(not sure).[/hide]

Title: Re: Maximum zeros
Post by towr on Mar 9^th, 2008, 3:11am

[hide]
1: start at the top right
2: move left until you meet the first one or leave the bound of the matrix
3: if you made at least one step left save the index of the row
4: move down until you meet the first zero or leave the bounds of matrix
5: goto 2 unless you left bounds of the matrix
6: return the saved row index
[/hide]