Algorithm for two piles of equal heights by removing boxes at top or bottom

Question

Assume you have two piles, each made of N boxes of different heights. You want to remove boxes so as to obtain two piles of equal heights (if possible). You cannot remove a box which is not at the top or the bottom of the pile! One can see for instance that if we remove the red boxes below we obtain two towers of equal heights:

Another way to state this problem is: given two arrays of positive numbers, are there two consecutive sub-sequences (one in each array) whose sums are equal?

This problem looks similar to this one, in which we have an array A of size N and a target t, and we want to find a consecutive sub-sequence of A whose sum is t (equivalently, we have a single pile of boxes and we want to remove boxes at the top and the bottom so as to obtain a pile of height t). This problem can be solved in time O(N). On the other hand, the above-mentioned problem has a trivial O(N^2) solution (see the answers below), but is there also a o(N^2) algorithm (O(N log N) for instance)?

Addendum: The sizes of the boxes are positive integers. They are assumed to be all differents (otherwise the problem can be trivially solved in O(N)). If we denote by H the total size of the two piles, there is a O(H log H) algorithm (see the answers below). Thus, the problem starts to be interesting for H greater than N (an efficient solution for H = N^2 would be a good start ;)

Answer 1

Let's find all the sums in O(n^2) and add them to a hash table:

for l in [0, n)
    cur_sum = 0
    for r in [l, n)
         cur_sum += a[r]
         hash_table.add(cur_sum)

After that, we need to do the same thing for the second array and check if at least one sum occurs in the hash table.

That's much better than a naive O(n^3) solution.

It's also possible to solve this problem in O(H log H) time, where H is the sum of boxes' heights if all heights are integers, but it's useful only if the total height is limited.

The O(H log H) solution goes like this:

We can find all subarray sums quickly. Let's take a look at what a subarray S sum is. It's a difference of two prefix sums P[r] - P[l] = S. If we add H to both sides of the equation, we obtain P[r] + (H - P[l]) = H + S. So we need to check if there exist two elements in the array P[i] and H - P[i], respectively, that add up to a given value. Let's not just check their existence, but count the number of such pairs. No it looks exactly like a multiplication of two polynomials. The coefficients of the first polynomial are the number of occurrences of a specific prefix sum (C[i] = count(j: P[j] == i)). The second polynomial is essentially the same thing reversed. We can multiply these two polynomials in O(H log H) time using Fourier fast transform (as they both are of degree H). After that, we just need to check the H + i coefficient of the product is non-zero.

Once we know all sums for the first and the second array, we need to check if they have at least one in common.