LeetCode 1537 - Get the Maximum Score

Difficulty: 🔴 Hard
Topics: Array, Two Pointers, Dynamic Programming, Greedy

Solution

Here’s a complete, detailed technical solution guide for LeetCode 1537 - Get the Maximum Score following your requested format.

Problem Understanding

The problem gives us two strictly increasing arrays of integers, nums1 and nums2, and asks us to compute the maximum sum obtainable along a valid path. A valid path starts from either array and moves left-to-right. When encountering a value that exists in both arrays, we can switch arrays. Each number contributes to the score only once along the path.

Our task is to compute the maximum sum of all possible paths, modulo $10^9 + 7$.

Key points to note:

Arrays are sorted and distinct, which allows for efficient traversal and comparison.
Switching arrays is only allowed at common elements.
Input size can be up to $10^5$, and element values up to $10^7$, which rules out brute-force recursion of all paths due to exponential combinations.
Edge cases include arrays with no intersection, arrays with all elements identical, and arrays of minimum size (length 1).

The core challenge is choosing when to switch arrays to maximize the sum, without having to enumerate every path explicitly.

Approaches

Brute Force Approach: A naive approach is to recursively explore all possible paths starting from both arrays. At each step, we can either continue in the same array or switch arrays if the current element exists in both. While this will produce the correct answer, the time complexity is exponential, $O(2^n)$, which is infeasible for $n$ up to $10^5$.

Optimal Approach: The key observation is that since arrays are sorted, we can use two pointers to traverse both arrays simultaneously. We maintain cumulative sums along each array separately. When we encounter a common element, we add the maximum cumulative sum from either array to the total, and then reset the individual cumulative sums beyond this intersection. This greedy approach ensures we always take the optimal sub-path at each intersection and reduces the problem to linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Explore all paths recursively, infeasible for large arrays
Optimal	O(n + m)	O(1)	Two-pointer traversal with cumulative sums, linear time, constant extra space

Algorithm Walkthrough

Initialize two pointers, i for nums1 and j for nums2, both starting at 0.
Maintain two cumulative sums, sum1 and sum2, representing the sum of values collected along nums1 and nums2 respectively since the last intersection.
Traverse both arrays simultaneously:
If nums1[i] < nums2[j], add nums1[i] to sum1 and increment i.
If nums1[i] > nums2[j], add nums2[j] to sum2 and increment j.
If nums1[i] == nums2[j], add the maximum of sum1 and sum2 plus the current value to a total_sum. Then reset sum1 and sum2 to 0. Increment both i and j.
After the loop, if any elements remain in either array, add their remaining sum to sum1 or sum2.
Add the maximum of sum1 and sum2 to total_sum and return it modulo $10^9 + 7$.

Why it works: The two-pointer method works because arrays are sorted. At each intersection, the greedy choice of taking the maximum cumulative sum ensures that all optimal sub-paths are preserved, and no better path is possible beyond this point without including elements from one of the two paths.

Python Solution

from typing import List

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        MOD = 10**9 + 7
        i, j = 0, 0
        sum1, sum2 = 0, 0
        total_sum = 0
        n, m = len(nums1), len(nums2)
        
        while i < n and j < m:
            if nums1[i] < nums2[j]:
                sum1 += nums1[i]
                i += 1
            elif nums1[i] > nums2[j]:
                sum2 += nums2[j]
                j += 1
            else:
                total_sum += max(sum1, sum2) + nums1[i]
                sum1 = 0
                sum2 = 0
                i += 1
                j += 1
        
        # Add remaining elements in either array
        while i < n:
            sum1 += nums1[i]
            i += 1
        while j < m:
            sum2 += nums2[j]
            j += 1
        
        total_sum += max(sum1, sum2)
        return total_sum % MOD

Explanation: The Python code directly implements the algorithm. sum1 and sum2 track cumulative sums along each array until an intersection occurs. At intersections, the maximum is added to total_sum. Remaining elements are handled after traversal.

Go Solution

func maxSum(nums1 []int, nums2 []int) int {
    const MOD = int(1e9 + 7)
    i, j := 0, 0
    sum1, sum2, totalSum := 0, 0, 0
    n, m := len(nums1), len(nums2)
    
    for i < n && j < m {
        if nums1[i] < nums2[j] {
            sum1 += nums1[i]
            i++
        } else if nums1[i] > nums2[j] {
            sum2 += nums2[j]
            j++
        } else {
            totalSum += max(sum1, sum2) + nums1[i]
            sum1, sum2 = 0, 0
            i++
            j++
        }
    }
    
    for i < n {
        sum1 += nums1[i]
        i++
    }
    for j < m {
        sum2 += nums2[j]
        j++
    }
    
    totalSum += max(sum1, sum2)
    return totalSum % MOD
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Go-specific notes: Go uses int types; the max function is defined separately. Slices handle remaining elements similarly to Python lists. Overflow is avoided by applying modulo at the final step.

Worked Examples

Example 1: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]

i	j	sum1	sum2	nums1[i]	nums2[j]	Action	total_sum
0	0	0	0	2	4	sum1+=2	0
1	0	2	0	4	4	intersection, total_sum += max(2,0)+4=6	6
2	1	0	0	5	6	sum1+=5	6
3	1	5	0	8	6	sum2+=6	6
3	2	5	6	8	8	intersection, total_sum+=max(5,6)+8=14	20
4	3	0	0	10	9	sum1+=10, sum2+=9	20
5	4	10	9	-	-	end, add max(10,9)=10	30

Result = 30

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Each array is traversed once with two pointers
Space	O(1)	Only a constant number of variables are used for sums and pointers

Because we only traverse each array linearly and store a fixed number of integers, this is optimal for the input constraints.

Test Cases

# Provided examples
assert Solution().maxSum([2,4,5,8,10], [4,6,8,9]) == 30  # intersection multiple times
assert Solution().maxSum([1,3,5,7,9], [3,5,100]) == 109  # intersection then large number
assert Solution().maxSum([1,2,3,4,5], [6,7,8,9,10]) == 40  # no intersection

# Edge/boundary cases
assert Solution().maxSum([1], [1]) == 1  # minimal size, single common element
assert Solution().maxSum([1], [2]) == 2  # minimal size, no intersection
assert Solution().maxSum([1,4,5], [2,3,6]) == 15