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 <kp101...@gmail.com> 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 <ankurga...@gmail.com> 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 <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. >> > > -- > 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.
