however maximum subarray can be found in O(n) just needs to get maximum difference in entries of each A[i] [-2]->[5] [-1]->[0, 2, 4, 6] maxdiff[-1] = 6-0 [0]->[-1, 1, 3, 7] maxdiff[0] = 7-(-1) [1]->[8, 10] maxdiff[1] = 10-8 [2]->[9] max(maxdiff[i]) = 8
surender On Sun, Sep 11, 2011 at 4:31 PM, Ankur Garg <[email protected]> wrote: > Yeah :( > U r right dude ...I dont think O(n) solution can exist for this problem > > > > On Sun, Sep 11, 2011 at 4:27 PM, Kunal Patil <[email protected]> wrote: > >> 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. >> > > -- > 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.
