Case 1 Start: 0 1 1 1 1 1 1 1 1 After first scan: 0 1 0 1 1 1 0 1 1
After second scan: 0 1 0 0 1 1 0 1 1 After third scan: 0 0 0 0 1 1 0 1 1 Case 2 Start: 1 1 0 1 1 1 0 1 1 After first scan: 0 1 0 1 1 1 0 1 0 After second scan: 0 0 0 0 1 1 0 0 0 After third scan: 0 0 0 0 1 0 0 0 0 Hope this helps. Dave On Nov 22, 9:34 am, "chandra kumar" <[EMAIL PROTECTED]> wrote: > Hi Dave, > Can you explain your algo for these 2 cases... > > 0 1 1 1 1 0 > 1 1 1 1 1 1 > 1 1 1 0 1 1 > > Please explain me in steps cause we tried the same problem and can't get > it done for without using extra space. ( we used 1 extra space, if the > array can contain only 0 or 1 and no other number, otherwise we store some > other number indicating a yet to become zero and proceed, in the later case > we need no extra space ) > Thanks and Regards, > K.V.Chandra Kumar > > On 15/11/2007, Dave <[EMAIL PROTECTED]> wrote: > > > > > > > Scan the array. If the i,j element is zero, set the last element of > > row i and the last element of column j to zero. Then, scan the last > > row, ignoring the last element, and zero every column that ends with a > > zero. Similarly, scan the last column, ignoring the last element, and > > zero every row that ends with a zero. This touches every element at > > most 3 times; i.e., if the array has m rows and n columns, the > > algorithm is O(1) in space and O(m*n) in time. > > > Dave > > > On Nov 14, 1:27 pm, geekko <[EMAIL PROTECTED]> wrote: > > > Given an array of 0's and 1's whenever you encounter an 0 make > > > corresponding column and row elements 0. How could you do that > > > efficiently(minimum time and minimum space complexity)? This question > > > is taken from placementsindia.blogspot.com- Hide quoted text - > > - Show quoted text - --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
