As the author correctly mentions it: "Building the array is O(n) , but printing these intervals must be done in linear time to the number of intervals." Assuming n means number of elements in the original array There are O(n^2) possible intervals, how can you print them in O(n) ???
On Sun, Sep 11, 2011 at 4:20 PM, Ankur Garg <[email protected]> wrote: > This solution is not in O(n) time :( > Unfortunately interviewer wants O(n) . > > > On Sun, Sep 11, 2011 at 4:01 PM, Kunal Patil <[email protected]> wrote: > >> @Brijesh: +1 >> >> >> On Sun, Sep 11, 2011 at 2:14 PM, Brijesh <[email protected]>wrote: >> >>> This is the fastest way I can think of to do this, and it is linear to >>> the number of intervals there are. >>> >>> Let L be your original list of numbers and A be a hash of empty arrays >>> where initially A[0] = [0] >>> >>> sum = 0 >>> for i in 0..n >>> if L[i] == 0: >>> sum-- >>> A[sum].push(i) >>> elif L[i] == 1: >>> sum++ >>> A[sum].push(i) >>> >>> Now A is essentially an x y graph of the sum of the sequence (x is the >>> index of the list, y is the sum). Every time there are two x values x1 and >>> x2 to an y value, you have an interval (x1, x2] where the number of 0s and >>> 1s is equal. >>> >>> There are m(m-1)/2 (arithmetic sum from 1 to m - 1) intervals where the >>> sum is 0 in every array M in A where m = M.length >>> >>> Using your example to calculate A by hand we use this chart >>> >>> L # 0 1 0 1 0 0 1 1 1 1 0 >>> A keys 0 -1 0 -1 0 -1 -2 -1 0 1 2 1 >>> L index -1 0 1 2 3 4 5 6 7 8 9 10 >>> >>> (I've added a # to represent the start of the list with an key of -1. >>> Also removed all the numbers that are not 0 or 1 since they're just >>> distractions) A will look like this: >>> >>> [-2]->[5] >>> [-1]->[0, 2, 4, 6] >>> [0]->[-1, 1, 3, 7] >>> [1]->[8, 10] >>> [2]->[9] >>> >>> For any M = [a1, a2, a3, ...], (ai + 1, aj) where j > i will be an >>> interval with the same number of 0s as 1s. For example, in [-1]->[0, 2, 4, >>> 6], the intervals are (1, 2), (1, 4), (1, 6), (3, 4), (3, 6), (5, 6). >>> >>> Building the array A is O(n), but printing these intervals from A must be >>> done in linear time to the number of intervals. In fact, that could be your >>> proof that it is not quite possible to do this in linear time to n because >>> it's possible to have more intervals than n and you need at least the number >>> of interval iterations to print them all. >>> >>> Unless of course you consider building A is enough to find all the >>> intervals (since it's obvious from A what the intervals are), then it is >>> linear to n >>> >>> THis is the solution..go through it, its very easy to understand... >>> PS: copied from >>> >>> http://stackoverflow.com/questions/6967853/dynamic-programming-can-interval-of-even-1s-and-0s-be-found-in-linear-time >>> >>> >>> >>> >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To view this discussion on the web visit >>> https://groups.google.com/d/msg/algogeeks/-/wM8Xhc1tUXQJ. >>> >>> 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. > -- 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.
