Dynamic programming: can interval of even 1's and 0's be found in linear time?

Question

Found the following inteview q on the web:

You have an array of 0s and 1s and you want to output all the intervals (i, j) where the number of 0s and numbers of 1s are equal. Example

    pos = 0 1 2 3 4 5 6 7 8
          0 1 0 0 1 1 1 1 0

One interval is (0, 1) because there the number of 0 and 1 are equal. There are many other intervals, find all of them in linear time.

I think there is no linear time algo, as there may be n^2 such intervals. Am I right? How can I prove that there are n^2 such ?

Answer 1

Every interval will contain at least one sequence of either (0,1) or (1,0). Therefore, it's simply a matter of finding every occurance of (0,1) or (1,0), then for each seeing if it is adjacent to an existing solution or if the two bookend elements form another solution.

With a bit of storage trickery you will be able to find all solutions in linear time. Enumerating them will be O(N^2), but you should be able to encode them in O(N) space.

Answer 2

A linear solution is possible (sorry, earlier I argued that this had to be n^2) if you're careful to not actually print the results!

First, let's define a "score" for any set of zeros and ones as the number of ones minus the number of zeroes. So (0,1) has a score of 0, while (0) is -1 and (1,1) is 2.

Now, start from the right. If the right-most digit is a 0 then it can be combined with any group to the left that has a score of 1. So we need to know what groups are available to the left, indexed by score. This suggests a recursive procedure that accumulates groups with scores. The sweep process is O(n) and at each step the process has to check whether it has created a new group and extend the table of known groups. Checking for a new group is constant time (lookup in a hash table). Extending the table of known groups is also constant time (at first I thought it wasn't, but you can maintain a separate offset that avoids updating each entry in the table).

So we have a peculiar situation: each step of the process identifies a set of results of size O(n), but the calculation necessary to do this is constant time (within that step). So the process itself is still O(n) (proportional to the number of steps). Of course, actually printing the results (either during the step, or at the end) makes things O(n^2).

I'll write some Python code to test/demonstrate.

Here we go:

SCORE = [-1,1]

class Accumulator:

    def __init__(self):
        self.offset = 0
        self.groups_to_right = {} # map from score to start index
        self.even_groups = []
        self.index = 0

    def append(self, digit):
        score = SCORE[digit]
        # want existing groups at -score, to sum to zero
        # but there's an offset to correct for, so we really want
        # groups at -(score+offset)
        corrected = -(score + self.offset)
        if corrected in self.groups_to_right:
            # if this were a linked list we could save a reference
            # to the current value.  it's not, so we need to filter
            # on printing (see below)
            self.even_groups.append(
                (self.index, self.groups_to_right[corrected]))
        # this updates all the known groups
        self.offset += score
        # this adds the new one, which should be at the index so that
        # index + offset = score (so index = score - offset)
        groups = self.groups_to_right.get(score-self.offset, [])
        groups.append(self.index) 
        self.groups_to_right[score-self.offset] = groups
        # and move on
        self.index += 1
        #print self.offset
        #print self.groups_to_right
        #print self.even_groups
        #print self.index

    def dump(self):
        # printing the results does take longer, of course...
        for (end, starts) in self.even_groups:
            for start in starts:
                # this discards the extra points that were added
                # to the data after we added it to the results
                # (avoidable with linked lists)
                if start < end:
                    print (start, end)

    @staticmethod
    def run(input):
        accumulator = Accumulator()
        print input
        for digit in input:
            accumulator.append(digit)
        accumulator.dump()
        print

Accumulator.run([0,1,0,0,1,1,1,1,0])

And the output:

dynamic: python dynamic.py 
[0, 1, 0, 0, 1, 1, 1, 1, 0]
(0, 1)
(1, 2)
(1, 4)
(3, 4)
(0, 5)
(2, 5)
(7, 8)

You might be worried that some additional processing (the filtering for start < end) is done in the dump routine that displays the results. But that's because I am working around Python's lack of linked lists (I want to both extend a list and save the previous value in constant time).

It may seem surprising that the result is of size O(n^2) while the process of finding the results is O(n), but it's easy to see how that is possible: at one "step" the process identifies a number of groups (of size O(n)) by associating the current point (self.index in append, or end in dump()) with a list of end points (self.groups_to_right[...] or ends).

Update: One further point. The table of "groups to the right" will have a "typical width" of sqrt(n) entries (this follows from the central limit theorem - it's basically a random walk in 1D). Since an entry is added at each step, the average length is also sqrt(n) (the n values shared out over sqrt(n) bins). That means that the expected time for this algorithm (ie with random inputs), if you include printing the results, is O(n^3/2) even though worst case is O(n^2)

Answer 3

Answering directly the question:

you have to constructing an example where there are more than O(N) matches:

let N be in the form 2^k, with the following input:

 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1  (here, N=16)

number of matches (where 0 is the starting character):

length    #
2         N/2 
4         N/2 - 1
6         N/2 - 2
8         N/2 - 3
..
N         1

The total number of matches (starting with 0) is: (1+N/2) * (N/2) / 2 = N^2/8 + N/4

The matches starting with 1 are almost the same, expect that it is one less for each length.

Total: (N^2/8 + N/4) * 2 - N/2 = N^2/4

Answer 4

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 :P