Suppose matrix is 1 0 0 1 1 0 1 0 0 0 0 0
then we traverse the matrix for each 1 we found at a[i][j] , we will check for i=i to i<row and j=j to j<col if that contains any more 1.... if it contains 1 in row then we don't make the whole row as 1..we ignore the row .... and same will be for column if it don't contains any other 1 after that (i,j) location then we make the whole row as 1...... and same will be for column .... i know this is not in O(mn) but i just want to check if my logic is correct or not...because it can be used somewhere else... ..... On Tue, Sep 27, 2011 at 11:51 AM, Gene <[email protected]> wrote: > 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. > > -- 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.
