Maximum sum path across two sorted arrays

I would check the statement first. Are both arrays sorted in strictly increasing order, so a value never repeats inside one array? Can values be negative? Does the path have to run to the end of the array it is on, and may it start in either array? When a value appears in both arrays, is it counted once? And is the answer the exact sum or a sum modulo a prime, since the sums can be very large?

The reports give one sample pair, sorted and without repeats, so I take that as the contract. I solve this version: both arrays are strictly increasing, the path starts at the first element of either array and moves right until it runs off the end, it may hop to the other array at any shared value, shared values count once, and I return the exact sum. The LeetCode version takes the result modulo 1,000,000,007, which I would apply only at the very end. The target is O(n + m) time and O(1) extra space.

Enumerate every path. Start in each array and walk right; at every shared value, branch into two paths, one that stays and one that hops to the other array. Sum each complete path and keep the maximum. Finding the matching index in the other array needs a search or a hash map.

With c shared values there are about 2 to the power c paths, each costing O(n + m) to add up, so the time is exponential. Memoising on the position fixes that, because the best sum from a position onward depends only on the position. That gives O(n + m) time but needs a map from values to indices and an array of results, so O(n + m) space, which misses the O(1) space target.

The pattern is two pointers merging two sorted arrays while accumulating segment sums. The shared values cut both arrays into aligned segments. Between two consecutive shared values, each array holds its own stretch of numbers, and a path walks through exactly one of the two stretches. Whichever it picks, it arrives at the next shared value at the same point, so the choices in different segments do not affect each other.

That makes the decision local: in every segment take the larger of the two stretch sums. The answer is the sum of all shared values plus, for each segment, the larger stretch sum; the last segment, after the final shared value, ends where the arrays end.

The merge walk computes it in one pass. Keep sumA and sumB, the best sums of paths that end at the last consumed element of each array, with 0 before anything is consumed. Compare the current elements: the smaller one belongs to a stretch, so add it to its own array's sum and advance that pointer. When they are equal it is a shared value: the best path reaching it is max(sumA, sumB) plus the value, and from here both arrays continue from that same best, so set both sums to it and advance both pointers. When one array runs out, add the rest of the other to its sum, and the answer is max(sumA, sumB).

Each element is touched once, so time is O(n + m), and only two sums are stored, so extra space is O(1). Out loud: "merge the arrays, add stretches to their own sum, and at every shared value collapse both sums to the larger one plus the value."

Take a = [2,4,5,8,10] and b = [4,6,8,9], with both sums at 0. Compare 2 and 4: 2 is smaller, so sumA becomes 2. Compare 4 and 4: shared, so both sums become max(2, 0) + 4 = 6. Compare 5 and 6: take 5, so sumA is 11 while sumB stays 6. Compare 8 and 6: take 6 for b, so sumB is 12.

Compare 8 and 8: shared, so both sums become max(11, 12) + 8 = 20. Compare 10 and 9: take 9 for b, so sumB is 29 and b is exhausted. The rest of a is 10, so sumA becomes 30. The answer is max(30, 29) = 30, from the path 2, 4, 6, 8, 10.

If one array is empty there are no shared values, and the answer is the sum of the other. If both are empty the answer is 0. With no shared values the answer is the larger of the two array sums. Identical arrays share every value and the answer is the sum of one of them, with every value counted once.

• Shared value at the very start or end: the equal branch handles it, adding the value once.
• Negative values: the logic never assumes positives, so a negative stretch simply loses to a better one; the path still must run to the end.
• One array inside the other: every value of the small one is shared, and the tails of the large one decide the end.
• Single-element arrays: the loop runs at most once.
• Large sums: totals can pass 2 to the power 53 for huge inputs; use BigInt then, and take any modulus only at the end.

The first slip is counting a shared value twice, once from each array, which inflates every junction. The second is resetting the sums to zero at a junction instead of setting both to the best sum plus the shared value, which throws away the earlier part of the path.

Others: taking the modulus while comparing sums, which can pick the smaller true sum; forgetting the tails after one array runs out; collapsing the equal case into a less-than-or-equal branch so that the pointers drift apart; moving only one pointer at a shared value; and reaching for a hash set of the shared values, which works but spends O(n) space when the question asked for O(1).