Solution: Get the Maximum Score

Statement

You are given two sorted arrays of distinct integers, nums1 and nums2.

A valid path is constructed according to the following rules:

• You start at the index $0$ of either nums1 or nums2.

• From there, you must traverse the chosen array from left to right.

• Suppose you encounter a number in both arrays (a common element, not necessarily at the same index). In that case, you may choose to switch to the other array at that element and continue the traversal from that point forward.

• A common element can only be counted once in the total path score, regardless of the array it appears.

The score of a path is defined as the sum of all unique elements visited during traversal. Your task is to return the maximum possible score achievable by any valid path. As the answer may be too large, return the maximum score modulo $10^{9}+7$.

Constraints:

• 1 $\leq$ nums1.length, nums2.length $\leq$ $10^{5}$

• 1 $\leq$ nums1[i], nums2[i] $\leq$ $10^{7}$

• All elements in nums1 and nums2 are strictly increasing.

Solution

The goal is to collect the maximum score by traversing two sorted arrays where switching between them is only allowed at common elements. The challenge is to choose when to switch to maximize the cumulative score.

This is done efficiently using the two pointers technique, which allows simultaneous traversal of both arrays in linear time, without the need to build or store all possible paths. As the arrays are strictly increasing, any prefix sum is guaranteed to grow as we move forward. At each common element, we are allowed to switch arrays. We decide whether to switch by comparing the scores accumulated from both paths and choosing the larger one as the new base to continue forward. This decision ensures that we always continue on the more rewarding path, step by step.

This approach works reliably because, beyond any common element, both arrays are still strictly increasing. So, regardless of which array we continue from, the score will continue to grow. We guarantee that the optimal path is preserved by always choosing the higher cumulative score at a common value. Let’s take an example to further understand this:

• nums1 $= [10, 20, 40, 50, 60]$

• nums2 $= [1, 2, 40, 10000, 35000]$

At the first common element $40$, we compare the cumulative sums collected so far:

• From sum_path1: $10 + 20 = 30$

• From sum_path2: $1 + 2 = 3$

As $30 > 3$, we take the maximum sum_path1 sum and add the common value $40$ to get $70$, then assign this to both paths, sum_path1 and sum_path2. This synchronization means both paths now carry the same score forward, ensuring we don’t miss high-value segments in either array, like nums2 having $10000$ next. The higher-sum path will naturally take the lead. Once both arrays are fully processed, we simply return the greater of the two running totals. This method avoids generating every possible path and instead builds the optimal one on-the-fly in linear time, making it both elegant and efficient.

Now, let’s look at the solution steps below:

1. Initialize two pointers, pointer1 and pointer2, to traverse nums1 and nums2, respectively.

2. Initialize two running sums, sum_path1 and sum_path2, to track the current total score on each path.

3. Define a constant MOD = 10^9 + 7 to apply modulo as required by the problem constraints to prevent overflow.

4. Traverse both arrays simultaneously using the two pointers, continuing until both pointers have reached the end of their respective arrays:

   1. If nums1[pointer1] $<$ nums2[pointer2]:

      1. Add nums1[pointer1] to sum_path1 and increment pointer1.

   2. Else if nums1[pointer1] $>$ nums2[pointer2]:

      1. Add nums2[pointer2] to sum_path2 and increment pointer2.

   3. Else (if nums1[pointer1] $==$ nums2[pointer2] (common element):

      1. Add the common value to the maximum of sum_path1 and sum_path2.

      2. Assign this computed sum to both sum_path1 and sum_path2 to synchronize paths.

      3. Increment both pointers to move past the common value in both arrays.

5. After traversal, take the maximum of sum_path1 and sum_path2.

6. Return the result modulo 10^9 + 7.

Let’s look at the following illustration to get a better understanding of the solution: