Make two arrays equal by merging neighbours into sums

You get two arrays a and b of positive integers. In either array you may, as many times as you like, replace a run of adjacent elements with a single element equal to their sum. Make the two arrays identical, keeping the result as long as possible, and return its length. If they can't be made equal, return -1.

Interface

Unless you agree on a different interface with the interviewer, assume:

• max_equal_length(a: list[int], b: list[int]) -> int — the length of the longest array both can be turned into, or -1.

Example

max_equal_length([11, 2, 3, 5, 7], [11, 7, 3, 7])  ->  3    # both become [11, 10, 7]
max_equal_length([1, 2], [100])                   ->  -1   # totals differ
max_equal_length([1, 2, 3], [1, 2, 3])            ->  3    # already equal
max_equal_length([1, 3], [2, 2])                  ->  1    # only [4]

Constraints

• 1 <= len(a), len(b) <= 3 * 10^5; 1 <= a[i], b[i] <= 10^9.

Clarifying questions

• Are all values positive? (It matters: with zeros or negatives, prefix sums are no longer strictly increasing.)
• Can merges happen in both arrays, or only one?
• Do you want the resulting array too, or only its length?

What a strong answer covers

• Equality is impossible unless the totals are equal.
• Each final element ends at a cut point; a cut is possible in both arrays exactly where they share a prefix sum. So the answer is the number of prefix sums the two arrays have in common.
• With positive values the prefix sums strictly increase, so a two-pointer walk finds the common ones in O(n + m) time and O(1) extra space; a hash set also works.
• Why greedily cutting at every common prefix sum gives the longest result.
• Use 64-bit sums. Tests: equal arrays, unequal totals, a single element on one side.

Follow-ups

• Return the resulting array.
• The arrays may contain zeros. What changes?
• There are three arrays, or k arrays.