If you're given that it's a sparse matrix, then you must assume storage is in a sparse matrix data structure to get time less than O(mn).
In fact, if you assume the right data structure, then the operation can take O(1) time. For example if you say the structure is an array of sets of indices of the 1's in each row (so that L(i) is a list that contains j if and only if A(i,j) is a 1), then all you have to do is flip a bit saying the representation has changed, i.e. lookups will work differently. The old lookup is A(i,j) = if L(i) contains j then 1 else 0. The new lookup will be A(i,j) = if L(i) is nonempty or L(j) contains i then 1 else 0 You'd probably want to store the sets in hash tables so that lookups will remain O(1). Other choices might make more sense if A has special structure. On Sep 26, 6:41 pm, Ankur Garg <[email protected]> wrote: > 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 <[email protected]> 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 <[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. -- 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.
