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:
- Sort both arrays, which takes $O(N + M)$ time if we use counting sort, as the array elements are small.
- 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]$.
- 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).
- 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.