Skip to main content
Talentd

Get the Maximum Score - Solution & Explanation

HardArrayTwo PointersDynamic ProgrammingGreedy18 min readAsked at: Amazon, Microsoft, Intuit +2
Practice this problem

Problem Statement

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.

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.

Approach 1: Two Pointer Approach

This approach utilizes two pointers, each pointing to the start of the arrays nums1 and nums2. We traverse through both arrays simultaneously and add up the values until we find a common element. At each common element, we compare the sums accumulated from the start of an array to this common element, and choose the maximum sum path. This process continues until the end of both arrays. The solution uses the properties of sorted arrays and merges the advantage of dynamic decision making at each intersection.

The solution defines a function maxSum to traverse the arrays using two pointers. It keeps track of two sums: sum1 for array nums1 and sum2 for array nums2. When a common element is encountered, it updates both sums to the maximum of the two sums plus the common element's value. After the loop, it adds any remaining elements to the respective sums. Finally, it returns the modulo of the maximum of the two sums.

Code

PythonC++CJavaC#JavaScript

Python

C++

C

Java

C#

JavaScript

Complexity

The time complexity is O(m + n), where m and n are the lengths of nums1 and nums2. The space complexity is O(1) as we only use a constant amount of additional space.

Try this approach in the editor →

Approach 2: Dynamic Programming with Memoization

This approach employs dynamic programming, maintaining a 2D array where each position denotes the maximum score reachable up to that index on either array. The solution stores previously computed scores for paths to avoid recomputation, optimizing further on overlapped recursive calls. This method uses an auxiliary memoization approach to maintain scores for comparative paths.

This solution utilizes dynamic programming with memoization to repeatedly calculate the maximum score through potential paths. An auxiliary dictionary memo stores the solution for each path choice already computed, ensuring optimized lookup instead of recalculating overlapping sub-problems.

Code

PythonC++CJavaC#JavaScript

Python

C++

C

Java

C#

JavaScript

Complexity

The time complexity can be high due to possible overlapping subproblems, however memoization optimizes lookup. Space complexity is potentially O(m*n) due to memoization storage.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Two Pointer Approach

The time complexity is O(m + n), where m and n are the lengths of nums1 and nums2. The space complexity is O(1) as we only use a constant amount of additional space.

Dynamic Programming with Memoization

The time complexity can be high due to possible overlapping subproblems, however memoization optimizes lookup. Space complexity is potentially O(m*n) due to memoization storage.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two Pointer Greedy TraversalO(n + m)O(1)Best choice when arrays are sorted and switching only happens at equal values
Dynamic Programming with MemoizationO((n + m) log(n + m))O(n + m)Useful for understanding the state transitions between arrays or when modeling the problem recursively

Video Solution

1537. Get the Maximum Score | Leetcode Hard | 2 Pointer approach • Chhavi Bansal • 3,823 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Get the Maximum Score easy or hard?
Get the Maximum Score is rated Hard because the optimal insight is not immediately obvious. The challenge lies in recognizing that segments between intersections can be evaluated independently and solved with a greedy two-pointer traversal instead of brute-force path exploration.
Get the Maximum Score Python/Java solution
Most implementations follow the same pattern: maintain two pointers, accumulate segment sums, and add the maximum sum when encountering equal elements. This logic translates directly across Python, Java, C++, and other languages because it relies only on loops, comparisons, and arithmetic operations.
How to solve Get the Maximum Score in O(n)?
Traverse both sorted arrays using two pointers and maintain two running sums. When elements differ, move the pointer with the smaller value and add it to its segment sum. When a common value appears, add the maximum of the two segment sums plus the shared value to the result and reset the sums. This linear scan processes all elements once, giving O(n + m) time.
What is the best approach for Get the Maximum Score?
The optimal approach uses a two-pointer greedy traversal across both sorted arrays. Track the sum of elements collected in each array segment until a common value appears. At the intersection, add the larger segment sum plus the shared value to the result and reset the counters. This runs in O(n + m) time with O(1) extra space.
Is Get the Maximum Score asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at companies that test greedy reasoning and array traversal patterns. The question combines two pointers with path optimization, which is common in interviews at companies like Amazon and Google when evaluating algorithmic thinking.
What data structure is used in Get the Maximum Score?
The optimal solution primarily uses arrays with a two-pointer technique and running sums. No additional complex data structures are required. In alternative dynamic programming solutions, hash maps may be used to quickly locate matching values between arrays.
What is the time complexity of Get the Maximum Score?
The optimal solution runs in O(n + m) time where n and m are the lengths of the two arrays. Each pointer moves forward exactly once, so every element is processed at most one time. The space complexity is O(1) since only a few running sums and pointers are stored.

Ready to solve this problem?

Practice Get the Maximum Score with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Score of a Node Sequence