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 <[email protected]> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
