Get the Maximum Score: Two-Pointer Path Switching

You are given two sorted arrays of distinct integers, nums1 and nums2. A valid path starts at the beginning of either array and ends at the end of either array. At any value that appears in both arrays, you can switch from one array to the other. Your goal is to find the path with the maximum sum, and return that sum modulo 10^9 + 7.

This is LeetCode 1537: Get the Maximum Score, a hard problem that combines two-pointer traversal of sorted arrays with greedy decision-making at intersection points.

Why this problem matters

This problem teaches you how to use two pointers across two sorted sequences simultaneously. Instead of merging or searching, you walk both arrays in tandem and accumulate segment sums between shared values. The greedy choice at each intersection point is locally optimal, and the sorted structure guarantees that this local optimality leads to a global optimum. This same two-pointer-on-two-sorted-arrays technique appears in problems involving merging, intersection finding, and parallel sequence comparison.

The key insight

Both arrays are sorted and share some common elements. These shared values split each array into segments. Between two consecutive shared values (or between the start and the first shared value, or between the last shared value and the end), you accumulate sums independently along each array. At each shared value, you take the maximum of the two accumulated segment sums and add that to your running total. This greedy local decision gives the global optimum because the segments are independent, and you cannot do better than choosing the heavier segment each time.

The solution

def maxScore(nums1, nums2):
    MOD = 10**9 + 7
    i, j = 0, 0
    sum1, sum2 = 0, 0
    m, n = len(nums1), len(nums2)

    while i < m and j < n:
        if nums1[i] < nums2[j]:
            sum1 += nums1[i]
            i += 1
        elif nums1[i] > nums2[j]:
            sum2 += nums2[j]
            j += 1
        else:
            sum1 += nums1[i]
            sum2 += nums2[j]
            sum1 = sum2 = max(sum1, sum2)
            i += 1
            j += 1

    while i < m:
        sum1 += nums1[i]
        i += 1
    while j < n:
        sum2 += nums2[j]
        j += 1

    return max(sum1, sum2) % MOD

The two pointers i and j advance through nums1 and nums2 respectively. When the current values differ, you add the smaller value to its running sum and advance that pointer. When the values match, you have reached a shared intersection. You add the shared value to both sums, then set both sums to the maximum. This "collapses" the two paths into one, locking in the better choice for the segment you just finished. After the main loop, you drain whichever array still has elements, then return the max of the two final sums.

Visual walkthrough

The walkthrough shows three segments for the example nums1 = [2, 4, 5, 8, 10] and nums2 = [4, 6, 8, 9]. The common values 4 and 8 create three segments. In segment 1 (before value 4), nums1 gives sum 6 vs. nums2 gives sum 4, so you pick 6. In segment 2 (between 4 and 8), nums1 gives 13 vs. nums2 gives 14, so you pick 14. In segment 3 (after value 8), nums1 gives 10 vs. nums2 gives 9, so you pick 10. Total: 6 + 14 + 10 = 30.

Complexity analysis

Time: O(m + n). Each pointer advances at most m or n times respectively. Every element is visited exactly once.

Space: O(1). Only a fixed number of variables are used regardless of input size. No auxiliary data structures are needed.

The building blocks

1. Two-pointer traversal of sorted arrays

while i < m and j < n:
    if nums1[i] < nums2[j]:
        sum1 += nums1[i]
        i += 1
    elif nums1[i] > nums2[j]:
        sum2 += nums2[j]
        j += 1

When you have two sorted arrays and need to process their elements in order, you use two pointers advancing in lockstep. The smaller element gets processed first. This is the same merge logic from merge sort, adapted to accumulate sums instead of building an output array.

2. Greedy segment sum selection at intersections

    else:
        sum1 += nums1[i]
        sum2 += nums2[j]
        sum1 = sum2 = max(sum1, sum2)
        i += 1
        j += 1

When both pointers land on the same value, you have an intersection. At this point, both segment sums include the shared value. You pick the larger sum and assign it to both, effectively committing to the better path for the segment that just ended. From this point forward, both paths restart from equal footing.

Edge cases

• No common elements. The two arrays share nothing. You walk both to the end and return the larger total sum. The main loop handles this by never entering the else branch.
• One array is empty. The main loop is skipped entirely. The drain loops handle the non-empty array, and you return its full sum.
• All elements are common. Every step enters the else branch. At each element, you pick the max, which in this case is always the same value. The result is just the sum of the single shared sequence.
• Large sums. The problem asks for the result modulo 10^9 + 7. You only apply the modulo at the very end, not during accumulation, because intermediate comparisons need the true values.
• Single-element arrays. Works correctly since the pointers advance once and the drain loops handle any remainder.

From understanding to recall

The core pattern here is "two pointers walking two sorted arrays, accumulating segment sums, and making a greedy choice at each intersection." That is a compact idea, but reproducing the code from scratch means remembering several details: how to handle the three cases (less, greater, equal), how to collapse the sums at an intersection, how to drain the remaining elements, and where to apply the modulo.

Spaced repetition helps you internalize these details. After a few reviews spaced days apart, you will not need to re-derive the logic. You will just write it. The two-pointer merge pattern and greedy segment selection are reusable building blocks that appear in many problems involving sorted sequences.

Related posts

• 3Sum Closest - Two-pointer technique on sorted arrays
• Longest Common Subsequence - Working with two sequences and making optimal choices at shared elements
• Best Time to Buy and Sell Stock III - Greedy segment-based optimization

The problems above all share a common thread: making optimal decisions while traversing sequences. If you can internalize the building blocks from each one, the next problem in this family becomes much easier to tackle. CodeBricks breaks these patterns into drillable units so you can build lasting recall instead of re-learning every time.