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.
