@Rajnish, Your algorithm works fine. If I'm not wrong you want to differentiate between initial zeros(-1) and zeros(0) inserted by replacement.
As I said its a binary matrix, So what I meant was the array can contain only 0's and 1's. Sorry if it was not clear, but the most interesting part is when you can't have anything other than 0's and 1's in array. I have a solution which does this in O(n^2) time and O(1) space but I want to discuss it since I found it quite interesting. On Sun, Feb 27, 2011 at 12:03 PM, Rajnish <rajnish.i...@gmail.com> wrote: > 1.) Traverse the whole matrix and replace each 0 value with -1. > 2.) Traverse the matrix again,all the 1 values are replaced with 0 in > the row and column of the index where a -1 value is found. > 3.) Set all -1 values to zero and we have the output array. > time complexity: O(n^2) > space complexity: O(1) > > > On Feb 27, 2:29 am, gaurav gupta <1989.gau...@googlemail.com> wrote: > > A NxN binary matrix is given. If a row contains a 0 all element in the > > row will be set to 0 and if a column contains a 0 all element of the > > column will be set to 0. You have to do it in O(1) space. > > > > example : > > > > input array : > > > > 1 0 1 1 0 > > 0 1 1 1 0 > > 1 1 1 1 1 > > 1 0 1 1 1 > > 1 1 1 1 1 > > > > result array : > > > > 0 0 0 0 0 > > 0 0 0 0 0 > > 0 0 1 1 0 > > 0 0 0 0 0 > > 0 0 1 1 0 > > > > Thanks & Regards, > > Gaurav Gupta > > -- > 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. > > -- Thanks & Regards, Gaurav Gupta "Quality is never an accident. It is always result of intelligent effort" - John Ruskin -- 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.
