DoubleHelix SPOJ

The problem, simply

You get two lists of numbers, both sorted from small to big. Some numbers appear in both lists. Those shared numbers are crossings.

You walk from the start to the end. You begin on either list and collect every number you step on. At a crossing you may switch to the other list and carry on from that same number. Find the biggest total you can collect. A crossing number is collected once.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every walk. At every crossing, the walk splits in two: stay or switch. A helper walk(a, i, b) returns the best total from position i of strand a to the end.

1. If i is past the end, return 0.
2. Option one: stay. Take a[i] and continue at i + 1 on the same strand.
3. If a[i] also appears in b at position k, option two: take a[i] and continue at k + 1 on strand b.
4. Return the better option. Start on either strand and keep the better start.

class Solution {
    // best total from a[i] to the end, allowed to jump at crossings
    long walk(int[] a, int i, int[] b) {
        if (i == a.length) return 0;
        long best = a[i] + walk(a, i + 1, b);              // stay on this strand
        for (int k = 0; k < b.length; k++) {
            if (b[k] == a[i]) {                             // a crossing: we may jump
                best = Math.max(best, a[i] + walk(b, k + 1, a));
            }
        }
        return best;
    }

    public long maxSum(int[] a, int[] b) {
        return Math.max(walk(a, 0, b), walk(b, 0, a));
    }
}

How long it takes: with k crossings there are about 2^k different walks, and each step of a walk scans the other strand for a match. That is roughly O(2^k * (n + m)^2). Extra room: the waiting calls, O(n + m).

Way 2: the clever way

The crossings cut both strands into stretches. Every walk passes every crossing, and between two crossings it uses one strand. The choice in one stretch does not change any other stretch. So for each stretch, take the richer strand.

Walk both sorted strands at once, like merging two sorted lists:

1. Fingers i and j start at 0. Sums sum1 and sum2 start at 0.
2. If a[i] < b[j], add a[i] to sum1 and move i. If b[j] < a[i], add b[j] to sum2 and move j.
3. If they are equal, it is a crossing. Add it to both sums, then add the bigger sum to total, reset both sums, and move both fingers.
4. When one strand runs out, add the rest of the other to its sum. Finish with total += max(sum1, sum2).

class Solution {
    public long maxSum(int[] a, int[] b) {
        int i = 0, j = 0;
        long sum1 = 0, sum2 = 0, total = 0;
        while (i < a.length && j < b.length) {
            if (a[i] < b[j]) {
                sum1 += a[i++];            // only on strand 1
            } else if (b[j] < a[i]) {
                sum2 += b[j++];            // only on strand 2
            } else {                       // a crossing
                total += Math.max(sum1 + a[i], sum2 + b[j]);
                sum1 = 0;
                sum2 = 0;
                i++;
                j++;
            }
        }
        while (i < a.length) sum1 += a[i++];   // leftovers after the last crossing
        while (j < b.length) sum2 += b[j++];
        return total + Math.max(sum1, sum2);
    }
}

How long it takes: each finger only moves forward, so every number is looked at once: O(n + m). Extra room: a few sums, O(1).

Watch out for

• Counting a crossing twice. Add it once, as part of the bigger sum.
• Comparing whole strands instead of stretches. The answer can mix strands: in the first example neither strand alone (69 or 106) gives 113.
• Values can be negative on the judge. The code still works because it compares real stretch sums. Do not "skip" a stretch because it is negative: every walk must pass through it.
• The judge input has many test cases and ends with a line that is just 0. Loop until you read it.

What interviewers ask next

• Why is the greedy choice safe? Every walk visits every crossing, so a walk is one choice per stretch, and the stretch sums add up independently. Picking the best of each stretch gives the best total.
• LeetCode "Get the Maximum Score" (1537) is the same problem with the answer taken modulo 10^9 + 7. Keep sums exact in long while comparing, and only take the modulo at the end, or the comparisons break.
• What if the lists are not sorted? Then "crossing order" is not defined by value. You would need positions and it becomes a path problem on a small graph, solved with dynamic programming.
• Three strands? Same idea, as long as a crossing means a number shared by all strands you could switch between. With partial crossings it becomes a longest path on a graph that has no loops.

Remember this

Grown-up words: walking two sorted lists together is the merge step with two pointers, the crossings are common elements, and banking the best stretch at each crossing is a greedy choice that is safe because the stretches are independent.