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.