This solution is not in O(n) time :( Unfortunately interviewer wants O(n) .
On Sun, Sep 11, 2011 at 4:01 PM, Kunal Patil <kp101...@gmail.com> wrote: > @Brijesh: +1 > > > On Sun, Sep 11, 2011 at 2:14 PM, Brijesh <brijeshupadhyay...@gmail.com>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 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. >> > > -- > 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. > -- 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.
