0814HardArrayTwo PointersDynamic ProgrammingGreedy

Best Total Across Two Ridges

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Two ridges each carry a line of cairns. west lists the altitudes of the cairns on the west ridge in the order they are met, and east does the same for the east ridge. Both lists are strictly increasing, so no ridge repeats an altitude, though an altitude may appear on both ridges.

A walker begins at the first cairn of either ridge and works upwards. From the cairn they are standing on they step to the next cairn of the ridge they are on. If the cairn they are standing on has an altitude that also appears on the other ridge, they may instead cross over and step to the cairn that follows that shared altitude on the other ridge. The walk ends when the walker steps past the last cairn of the ridge they are on.

The score of a walk is the sum of the altitudes of the cairns it stands on, each counted once. Return the highest score any walk can reach.

Examples

Example 1

Input: west = [3, 7, 12, 20], east = [7, 9, 12, 30]
Output: 61

One walk starts on the west ridge at 3 and 7, crosses at altitude 7, carries on over 9 and 12 on the east ridge and finishes there at 30. It stands on 3, 7, 9, 12 and 30, which total 61.

Example 2

Input: west = [2, 5, 11], east = [4, 6]
Output: 18

No altitude appears on both ridges, so no crossing is ever available and a walk covers one whole ridge. The west ridge totals 18 and the east ridge totals 10.

Example 3

Input: west = [8], east = [8]
Output: 8

Each ridge carries a single cairn at altitude 8, and a shared cairn counts once, so any walk scores 8.

Constraints

1 <= west.length, east.length <= 10^5
1 <= west[i], east[i] <= 10^7
west and east are strictly increasing.
The highest score is at most 10^13.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def best_ridge_total(west: list[int], east: list[int]) -> int:

Java

public long bestRidgeTotal(int[] west, int[] east)

The intended approach

Time O(n + m) for ridges of n and m cairns.Space O(1) beyond the inputs.

Shared altitudes are the only places a walk can change ridge, so they cut both ridges into matching stretches, and inside a stretch the walker has no choice at all. One pointer runs down each ridge; each pointer adds up the cairns it passes. When the two pointers meet on the same altitude, the better of the two running stretches is banked along with that shared cairn, counted once, and both running totals restart. Once either ridge runs out, the remainder of the other is added to its running total and the better trailing stretch is banked.

Pythonentry point: best_ridge_total

def best_ridge_total(west, east):
    # Between two consecutive shared altitudes the walker is locked onto one
    # ridge, so each such stretch can be settled on its own: run one pointer down
    # each ridge, add up the cairns each has passed since the last shared
    # altitude, and at a shared altitude bank the better of the two stretches
    # plus the shared cairn itself, counted once. The stretch after the last
    # shared altitude is banked the same way once a ridge runs out.
    #
    # Time: O(n + m). Space: O(1) beyond the inputs.
    n, m = len(west), len(east)
    i = j = 0
    run_w = run_e = 0
    total = 0
    while i < n and j < m:
        if west[i] < east[j]:
            run_w += west[i]
            i += 1
        elif east[j] < west[i]:
            run_e += east[j]
            j += 1
        else:
            total += (run_w if run_w > run_e else run_e) + west[i]
            run_w = run_e = 0
            i += 1
            j += 1
    while i < n:
        run_w += west[i]
        i += 1
    while j < m:
        run_e += east[j]
        j += 1
    return total + (run_w if run_w > run_e else run_e)

The obvious version

Settle the cairns in decreasing order of altitude, recording for each the best score reachable from it onwards: either carry on along its own ridge, or, when its altitude is shared, continue from the cairn after the match on the other ridge. Both options lie strictly higher, so every option is already settled. The answer is the better of the two first cairns.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_best_ridge_total(west, east):
    """Work backwards: the best total from each cairn onwards.

    From a cairn the walker either carries on along its own ridge or, when the
    altitude is shared, continues from the cairn after the matching one on the
    other ridge. Both options sit at a strictly higher altitude, so the cairns
    are settled in decreasing order of altitude and no cairn is ever visited
    before the options it depends on.
    """
    n, m = len(west), len(east)
    at_w = {v: i for i, v in enumerate(west)}
    at_e = {v: j for j, v in enumerate(east)}
    best_w = [0] * (n + 1)
    best_e = [0] * (m + 1)
    i, j = n - 1, m - 1
    while i >= 0 or j >= 0:
        if j < 0 or (i >= 0 and west[i] >= east[j]):
            opt = best_w[i + 1]
            k = at_e.get(west[i])
            if k is not None and best_e[k + 1] > opt:
                opt = best_e[k + 1]
            best_w[i] = west[i] + opt
            i -= 1
        else:
            opt = best_e[j + 1]
            k = at_w.get(east[j])
            if k is not None and best_w[k + 1] > opt:
                opt = best_w[k + 1]
            best_e[j] = east[j] + opt
            j -= 1
    return best_w[0] if best_w[0] > best_e[0] else best_e[0]

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in