{x}
blog image

Get the Maximum Score

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

A valid path is defined as follows:

  • Choose array nums1 or nums2 to traverse (from index-0).
  • Traverse the current array from left to right.
  • If you are reading any value that is present in nums1 and nums2 you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path).

The score is defined as the sum of unique values in a valid path.

Return the maximum score you can obtain of all possible valid paths. Since the answer may be too large, return it modulo 109 + 7.

 

Example 1:

Input: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
Output: 30
Explanation: Valid paths:
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],  (starting from nums1)
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]    (starting from nums2)
The maximum is obtained with the path in green [2,4,6,8,10].

Example 2:

Input: nums1 = [1,3,5,7,9], nums2 = [3,5,100]
Output: 109
Explanation: Maximum sum is obtained with the path [1,3,5,100].

Example 3:

Input: nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
Output: 40
Explanation: There are no common elements between nums1 and nums2.
Maximum sum is obtained with the path [6,7,8,9,10].

 

Constraints:

  • 1 <= nums1.length, nums2.length <= 105
  • 1 <= nums1[i], nums2[i] <= 107
  • nums1 and nums2 are strictly increasing.

Solution Explanation

This problem asks us to find the maximum score achievable by traversing either nums1 or nums2 from left to right, switching paths only when encountering a common element. The score is the sum of unique elements in the chosen path.

The optimal approach uses a greedy strategy combined with two pointers. We maintain two pointers, i and j, to track the current indices in nums1 and nums2 respectively. We also maintain two variables, f and g, representing the current scores for paths starting in nums1 and nums2, respectively.

The algorithm iterates as follows:

  1. No more elements in one array: If we reach the end of one array (i == m or j == n), we continue traversing the other array, adding the elements to the corresponding score (f or g).

  2. Compare elements: If both arrays still have elements, we compare nums1[i] and nums2[j].

    • If nums1[i] < nums2[j], we add nums1[i] to f and increment i.
    • If nums1[i] > nums2[j], we add nums2[j] to g and increment j.
    • If nums1[i] == nums2[j], it's a common element. We update both scores by adding the common element to the larger of the two current scores (max(f, g)), and increment both i and j. This ensures we consider the best path up to this point.

  3. Return the maximum: After processing all elements, the maximum score is max(f, g), which we return modulo 10^9 + 7.

Time Complexity: O(m + n), where m and n are the lengths of nums1 and nums2 respectively. We iterate through each array at most once.

Space Complexity: O(1). We only use a constant amount of extra space.

Code in Different Languages

The provided code snippets illustrate the algorithm in various programming languages: Python, Java, C++, Go, and TypeScript. All implementations follow the same logic described above. The mod operation ensures that the result is within the specified range. The max function is used to find the greater of the two scores, and the looping structure effectively implements the two-pointer greedy strategy.