Get the Maximum Score - Video Solutions
1537. Get the Maximum Score | Leetcode Hard | 2 Pointer approach
Get the Maximum Score - Video Solution
Watch 10 video solutions for Get the Maximum Score, a hard level problem involving Array, Two Pointers, Dynamic Programming. This walkthrough by Chhavi Bansal has 3,823 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given two sorted arrays of distinct integers nums1 and nums2.
A valid path is defined as follows:
- Choose array
nums1ornums2to traverse (from index-0). - Traverse the current array from left to right.
- If you are reading any value that is present in
nums1andnums2you 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 <= 1051 <= nums1[i], nums2[i] <= 107nums1andnums2are strictly increasing.
Approach Overview
Problem Overview: You are given two sorted arrays. You can traverse either array from left to right and switch to the other array whenever both contain the same value. The goal is to maximize the total sum of visited elements.
Approach 1: Two Pointer Greedy Traversal (O(n + m) time, O(1) space)
This approach exploits the fact that both arrays are sorted. Use two pointers to iterate through nums1 and nums2 simultaneously. Maintain two running sums representing the score collected along each array segment since the last intersection. When the values differ, advance the pointer with the smaller value and add it to its running sum. When both values match, you reach a switch point. Add the larger of the two running sums plus the common value to the final answer, then reset both sums. This greedy decision works because any path before the intersection is independent of future choices. Continue until both arrays are processed, then add the larger remaining segment sum. This method relies on sequential scanning using two pointers and simple arithmetic, making it both optimal and memory efficient.
Approach 2: Dynamic Programming with Memoization (O((n + m) log(n + m)) time, O(n + m) space)
Dynamic programming models the problem as choices between continuing in the same array or switching when encountering a shared value. Preprocess both arrays with a map from value to index so you can jump between arrays at intersections. Define a recursive state dp(i, arr) representing the maximum score starting from index i in a specific array. The recurrence accumulates values while moving forward and optionally jumps to the corresponding index in the other array when a shared element appears. Memoization stores computed states to avoid repeated work. This approach frames the problem using dynamic programming over indices and transitions. It is conceptually useful but less efficient than the linear greedy solution.
The key observation behind the optimal solution is that segments between intersections are independent. You only need to choose the larger accumulated sum before switching paths. That converts what looks like a path optimization problem into a simple greedy merge process across two arrays.
Recommended for interviews: The two pointer greedy approach is what interviewers expect. It demonstrates that you recognize the sorted structure and reduce the problem to linear traversal. Mentioning a DP formulation shows deeper understanding, but implementing the O(n + m) two-pointer solution proves strong algorithmic instincts.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointer Greedy Traversal | O(n + m) | O(1) | Best choice when arrays are sorted and switching only happens at equal values |
| Dynamic Programming with Memoization | O((n + m) log(n + m)) | O(n + m) | Useful for understanding the state transitions between arrays or when modeling the problem recursively |