DoubleHelix — maximum sum path across two arrays

Medium

Problem

Two sorted arrays share some values ("intersection points"). You walk through one array from left to right, and at any shared value you may switch to the other array and continue from that value. Return the largest possible sum of the values you visit.

Example 1

Input:  a = [3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62], b = [1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100]
Output: 450

Also asked as: DoubleHelix SPOJ

Test cases

Case 1

Input:    [3,5,7,9,20,25,30,40,55,56,57,60,62], [1,4,7,11,14,25,44,47,55,57,100]
Expected: 450

Case 2

Input:    [2,3,7,10,12], [1,5,7,8]
Expected: 35

Case 3

Input:    [1,2,3], [4,5,6]
Expected: 15

Case 4

Input:    [], []
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Merge with segment sums, switch at common elements

Time O(n + m)Space O(1)

Walk both sorted arrays with two pointers, accumulating a running sum for each. At a common value, add the larger of the two running sums to the total and reset both.

function doubleHelix(a, b) {
let i = 0, j = 0, sumA = 0, sumB = 0, total = 0;
while (i < a.length && j < b.length) {
if (a[i] < b[j]) sumA += a[i++];
else if (a[i] > b[j]) sumB += b[j++];
else {
total += Math.max(sumA, sumB) + a[i];
sumA = sumB = 0; i++; j++;
}
}
while (i < a.length) sumA += a[i++];
while (j < b.length) sumB += b[j++];
return total + Math.max(sumA, sumB);
}