Guys an Update ,
This has been asked in MS by me.. I suggested O(m*n) but they were looking
for a solution in nlogn ( n*n Sparse Matrix ) ..Any idea ...
This post was discussed earlier but every1 came with O(m*n) solution so
instead of cluttering it ..opened a new One ...
On Tue, Sep 27, 2011 at 3:06 AM, Gene <gene.ress...@gmail.com> wrote:
> I assume we don't want to use extra storage.
>
> So one way is this: Go over the matrix and mark the first row with a 1
> and the first column with a 1 for each 1 you find. Because row and
> column 1 are used for temporary storage in this manner, you must first
> remember whether they contained a 1, then go ahead. With row and
> column 1 holding the necessary marks, you can fill in all the rows and
> columns except them. Finally you can fill in row and column 1 by
> checking the saved values. It will look something like this.
>
> row0has1 = 0;
> for (j = 0; j < n; j++) if (M(0,j)) { row0has1 = 1; break; }
> col0has1 = 0;
> for (i = 0; i < n; i++) if (M(i,0)) { col0has1 = 1; break; }
> for (i = 1; i < m; i++)
> for (j = 1; j < n; j++)
> if (M(i,j)) M(i,0) = M(0,j) = 1;
> for (i = 1; i < m; i++)
> for (j = 1; j < n; j++)
> if (M(i,0) || M(0,j)) M(i, j) = 1;
> if (row0has1)
> for (j = 0; j < n; j++) M(0,j) = 1;
> if (col0has1)
> for (i = 0; i < n; i++) M(i,0) = 1;
>
> Maybe there's a slicker way, but this is O(mn)
>
> On Sep 26, 9:46 pm, Ankur Garg <ankurga...@gmail.com> wrote:
> > Saw this question in one of the algo communities.
> >
> > Amazon telephonic interview question on Matrix
> > Input is a matrix of size n x m of 0's and 1's. 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 space complexity =
> O(1)
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
