wu :: forums - Print Page


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

        riddles >> cs >> Make row/col 1 if element is 1 in a matrix.
        
(Message started by: Ved on Sep 4^th, 2011, 7:45am)

Title: Make row/col 1 if element is 1 in a matrix.
Post by Ved on Sep 4^th, 2011, 7:45am

Input is a matrix of size n x m of 0s and 1s.

eg:
1 0 0 1
0 0 1 0
0 0 0 0

If a location has 1; make all the elements of that row and column = 1. eg

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

Solution should be with Time complexity = O(n*m) and O(1) extra space

Title: Re: Make row/col 1 if element is 1 in a matrix.
Post by wiley on Sep 4^th, 2011, 8:33am

is it a binary matrix? Can we put some other number in matrix, say, 2.

Title: Re: Make row/col 1 if element is 1 in a matrix.
Post by wiley on Sep 4^th, 2011, 8:49am

One soln could be:
1 0 0 1
0 0 1 0
0 0 0 0

Step1: Bring 1 to first row and first column and set everywhere else to 0. O(n*m), we'll get:
1 0 1 1
1 0 0 0
0 0 0 0

Step2: Starting from 2nd column to last column, fill columns with 1:
1 0 1 1
1 0 1 1
0 0 1 1

Step3: Starting from first row to last row fill rows with 1:
1 1 1 1
1 1 1 1
0 0 1 1

Step4: Fill for column at first index:
1 1 1 1
1 1 1 1
1 0 1 1

Title: Re: Make row/col 1 if element is 1 in a matrix.
Post by towr on Sep 4^th, 2011, 11:56am

Nice solution. :)

The top-left corner has to be treated as an exception in step 1; for example if the left column is zero but the top row has a one somewhere, you don't want to set the top-left corner to 1, because then the left column would become one in step 4, which wouldn't be correct (unless every row had a 1 in it).

Title: Re: Make row/col 1 if element is 1 in a matrix.
Post by wiley on Sep 5^th, 2011, 7:30am

yeah.. i also got this missing case after posting the solution.. :)
we can handle it by keeping two boolean variables, say, isColumn and isRow and set them true as applicable.