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 --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
