Finding equal-sum subsets from two arrays

Question

Consider the following problem: You are given two integer arrays $A$ and $B$ of size $N$ and $M$, respectively. You are guaranteed that $1 <= A[i] <= M$ and $1 <= B[i] <= N$ for all $i$ (so each array's elements is at most the other array's size). The sizes of the arrays, $N$ and $M$, may be up to $100,000$. Construct two nonempty subsets, one from $A$, and one from $B$, that have the same sum. (Here subsets means sub-multi-set). There is apparently an $O(N + M)$ solution to this problem, but I don't know what it is.

My idea: First, I don't know if it is provable that two equal-sum subsets always exist... anyways:

1. Sort both arrays, which takes $O(N + M)$ time if we use counting sort, as the array elements are small.
2. Iterate through each array, and observe that all the possible subset sums will form contiguous ranges, so collect all contiguous ranges of possible subset sums. To do this, simply maintain the prefix sum $psum$ of the array so far, and then consider the current element $curr$. If $curr <= psum$, that means for any number $x \in [psum - curr, psum]$, we can also make the sum $x + curr$. If $curr > psum$, then we cannot make any sum $x \in (psum, curr]$.
3. After collecting all the ranges, iterate through them and find any two ranges that intersect from both arrays. Then, take a subset sum that both arrays can create, and the task reduces to finding a subset of the array which sums to that subset sum (which I also don't think can be done efficiently).
4. Another problem is, I found that the number of contiguous ranges of subsets can be quite large, growing quicker than $O(N)$ or $O(M)$.

So, I'm stuck.

I'm guessing that the conditions $1 <= A[i] <= M$ and $1 <= B[i] <= N$ allows for some mathematical proof that two equal-sum subsets always exist. I'd be very interested as to a proof of this, or any solutions to the problem that achieve close to the desired time complexity. I hope my line of reasoning has been clear so far.

Answer 1

The outline of some ideas.

Since it is too slow to run through all subsets, we may restrict to subarrays of $A$ and $B$. The sum of numbers in a subarray can be computed readily as the difference of two prefix-sums.

Towards two subarrays of equal sums, we would like to generate many pairs of prefix-sums, one from $A$ and the other from $B$ such that the difference in each pair is as small as possible. Then we might squeeze out two subarrays of equal sums when we have enough pairs with small differences.

A proof for the existence of two equal-sum subarrays

Let us use prefix sums and pigeonhole principle to prove that amazing fact.

Let $p_A$ be the prefix sums of $A$, i.e. $p_A[i]$ is the sum of the first $i$ numbers in $A$ for $0\le i\le N$. Ditto for $p_B$, the prefix sums of $B$.

Assume $p_B[M]\ge p_A[N]$. If not, switch $A, N$ with $B, M$ respectively.

For each $i$, $1\le i\le N$, let $$d(i)= p_B[g(i)]-p_A[i]$$ where $g(i)$ is the smallest $k$ such that $p_B[k]\ge p_A[i]$. $g(i)$ is well defined since $p_B[M]\ge p_A[N]\ge p_A[i]$.

For all $1\le i\le N$, $d(i)$ is one of $0,1,\cdots,N-1$ since

• $d(i)\ge0$ by definition.
• Since $g(i)$ is the smallest, we have $p_B[g(i)-1]$ $<p_A[i].$ So $d(i)$ $=(p_B[g(i)-1] +B[g(i)])-p_A[i]$ $< B[g(i)]$ $\le N$.

There are two cases.

• $d(i)=0$ for some $i$.
  The sum of the first $g(i)$ elements of $B$ is the same as the sum of the first $i$ elements of $A$.

• $d(i)$ is never $0$.
  One number from $1$ to $N-1$ must appear at least twice among $d(i)$'s, thanks to the pigeonhole principle. That is, there exist $e,f$ such that $d(e)=d(f)$. WLOG, $e<f$.

  The equality means the sum of numbers from the $e+1$-th number to the $f$-th number in $A$ is the same as the sum of numbers from the $e+1$-th number to the $f$-th number in $B$.

In both cases we have obtained two equal-sum subarrays.

Time-complexity analysis

The proof above implies an $O(M+N)$ algorithm immediately.

• Prefix sums for $A$ can be computed in $O(N)$ time. Ditto for $B$.
• The array $g$ can be computed in $O(M+N)$ time using two-pointer technique.
• $e$ and $f$ can be found in $O(N)$ time or $O(M)$ time.