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.