1537. Get the Maximum Score Solution & Code

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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 10⁹ + 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 <= 10⁵
1 <= nums1[i], nums2[i] <= 10⁷
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.

Python

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

Java

import java.util.List;
import java.util.ArrayList;

class Solution {
    public int maxSum(int[] nums1, int[] nums2) {
        final int MOD = 1_000_000_007;
        long sum1 = 0, sum2 = 0;
        int i = 0, j = 0, n = nums1.length, m = nums2.length;
        while (i < n || j < m) {
            if (i < n && (j == m || nums1[i] < nums2[j])) {
                sum1 += nums1[i++];
            } else if (j < m && (i == n || nums2[j] < nums1[i])) {
                sum2 += nums2[j++];
            } else { // both are equal
                sum1 = sum2 = Math.max(sum1, sum2) + nums1[i];
                i++; j++;
            }
        }
        return (int)(Math.max(sum1, sum2) % MOD);
    }
}

C++

#include <vector>
#include <algorithm>
using namespace std;

int maxSum(vector<int>& nums1, vector<int>& nums2) {
    const int MOD = 1e9 + 7;
    long sum1 = 0, sum2 = 0;
    int i = 0, j = 0, m = nums1.size(), n = nums2.size();
    while (i < m && j < n) {
        if (nums1[i] < nums2[j]) {
            sum1 += nums1[i++];
        } else if (nums1[i] > nums2[j]) {
            sum2 += nums2[j++];
        } else { // nums1[i] == nums2[j]
            sum1 = sum2 = max(sum1, sum2) + nums1[i];
            i++; j++;
        }
    }
    while (i < m) sum1 += nums1[i++];
    while (j < n) sum2 += nums2[j++];
    return max(sum1, sum2) % MOD;
}

JavaScript

var maxSum = function(nums1, nums2) {
    const MOD = 1e9 + 7;
    let sum1 = 0, sum2 = 0;
    let i = 0, j = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) {
            sum1 += nums1[i++];
        } else if (nums1[i] > nums2[j]) {
            sum2 += nums2[j++];
        } else {
            sum1 = sum2 = Math.max(sum1, sum2) + nums1[i];
            i++; j++;
        }
    }
    while (i < nums1.length) sum1 += nums1[i++];
    while (j < nums2.length) sum2 += nums2[j++];
    return Math.max(sum1, sum2) % MOD;
};

#include <stdio.h>
#define MOD 1000000007

int maxSum(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    long sum1 = 0, sum2 = 0;
    int i = 0, j = 0;
    while (i < nums1Size && j < nums2Size) {
        if (nums1[i] < nums2[j]) {
            sum1 += nums1[i++];
        } else if (nums1[i] > nums2[j]) {
            sum2 += nums2[j++];
        } else {
            sum1 = sum2 = (sum1 > sum2 ? sum1 : sum2) + nums1[i];
            i++; j++;
        }
    }
    while (i < nums1Size) sum1 += nums1[i++];
    while (j < nums2Size) sum2 += nums2[j++];
    return (int)((sum1 > sum2 ? sum1 : sum2) % MOD);
}

public class Solution {
    public int MaxSum(int[] nums1, int[] nums2) {
        const int MOD = 1000000007;
        long sum1 = 0, sum2 = 0;
        int i = 0, j = 0, n1 = nums1.Length, n2 = nums2.Length;
        while (i < n1 || j < n2) {
            if (i < n1 && (j == n2 || nums1[i] < nums2[j])) {
                sum1 += nums1[i++];
            } else if (j < n2 && (i == n1 || nums1[i] > nums2[j])) {
                sum2 += nums2[j++];
            } else { // nums1[i] == nums2[j]
                sum1 = sum2 = Math.Max(sum1, sum2) + nums1[i];
                i++; j++;
            }
        }
        return (int)(Math.Max(sum1, sum2) % MOD);
    }
}

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.

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.

Python

def maxSum(nums1, nums2):
    MOD = 10**9 + 7
    memo = {}
    def dp(i, j):
        if i == len(nums1) and j == len(nums2):
            return 0
        if (i, j) in memo:
            return memo[(i, j)]
        ans = 0
        if i < len(nums1):
            ans = max(ans, nums1[i] + dp(i + 1, j))
        if j < len(nums2):
            ans = max(ans, nums2[j] + dp(i, j + 1))
        if i < len(nums1) and j < len(nums2) and nums1[i] == nums2[j]:
            ans = max(ans, nums1[i] + dp(i + 1, j + 1))
        memo[(i, j)] = ans
        return ans
    return dp(0, 0) % MOD

Java

import java.util.HashMap;
import java.util.Map;

public class Solution {
    private Map<String, Long> memo = new HashMap<>();
    public int maxSum(int[] nums1, int[] nums2) {
        return (int)(dp(nums1, nums2, 0, 0) % 1_000_000_007);
    }

    private long dp(int[] nums1, int[] nums2, int i, int j) {
        if (i == nums1.length && j == nums2.length) return 0;
        String key = i + "," + j;
        if (memo.containsKey(key)) return memo.get(key);

        long ans = 0;
        if (i < nums1.length) ans = Math.max(ans, nums1[i] + dp(nums1, nums2, i + 1, j));
        if (j < nums2.length) ans = Math.max(ans, nums2[j] + dp(nums1, nums2, i, j + 1));
        if (i < nums1.length && j < nums2.length && nums1[i] == nums2[j])
            ans = Math.max(ans, nums1[i] + dp(nums1, nums2, i+1, j+1));

        memo.put(key, ans);
        return ans;
    }
}

C++

#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
class Solution {
    unordered_map<int, unordered_map<int, long>> memo;
public:
    int maxSum(vector<int>& nums1, vector<int>& nums2) {
        return (int)(dp(nums1, nums2, 0, 0) % 1000000007);
    }
private:
    long dp(vector<int>& nums1, vector<int>& nums2, int i, int j) {
        if (i == nums1.size() && j == nums2.size()) return 0;
        if (memo[i][j] != 0) return memo[i][j];
        long ans = 0;
        if (i < nums1.size()) ans = max(ans, nums1[i] + dp(nums1, nums2, i+1, j));
        if (j < nums2.size()) ans = max(ans, nums2[j] + dp(nums1, nums2, i, j+1));
        if (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j]) 
            ans = max(ans, nums1[i] + dp(nums1, nums2, i+1, j+1));
        memo[i][j] = ans;
        return ans;
    }
};

JavaScript

const maxSum = (nums1, nums2) => {
    const MOD = 1e9 + 7;
    const memo = new Map();
    const dp = (i, j) => {
        if (i === nums1.length && j === nums2.length) return 0;
        const key = `${i},${j}`;
        if (memo.has(key)) return memo.get(key);

        let ans = 0;
        if (i < nums1.length) ans = Math.max(ans, nums1[i] + dp(i + 1, j));
        if (j < nums2.length) ans = Math.max(ans, nums2[j] + dp(i, j + 1));
        if (i < nums1.length && j < nums2.length && nums1[i] === nums2[j])
            ans = Math.max(ans, nums1[i] + dp(i + 1, j + 1));

        memo.set(key, ans);
        return ans;
    };
    return dp(0, 0) % MOD;
};

#include <stdlib.h>
#include <string.h>

#define MOD 1000000007

int dp(int* nums1, int nums1Size, int* nums2, int nums2Size, int i, int j, long** memo)
{
    if (i == nums1Size && j == nums2Size) return 0;
    if (memo[i][j] != -1) return memo[i][j];
    long ans = 0;
    if (i < nums1Size) ans = max(ans, nums1[i] + dp(nums1, nums1Size, nums2, nums2Size, i+1, j, memo));
    if (j < nums2Size) ans = max(ans, nums2[j] + dp(nums1, nums1Size, nums2, nums2Size, i, j+1, memo));
    if (i < nums1Size && j < nums2Size && nums1[i] == nums2[j])
        ans = max(ans, nums1[i] + dp(nums1, nums1Size, nums2, nums2Size, i+1, j+1, memo));
    return memo[i][j] = (int)ans;
}

int maxSum(int* nums1, int nums1Size, int* nums2, int nums2Size)
{
    long** memo = (long**)malloc((nums1Size+1) * sizeof(long*));
    for (int i = 0; i <= nums1Size; i++) {
        memo[i] = (long*)malloc((nums2Size+1) * sizeof(long));
        memset(memo[i], -1, (nums2Size+1) * sizeof(long));
    }
    int result = dp(nums1, nums1Size, nums2, nums2Size, 0, 0, memo) % MOD;
    for (int i = 0; i <= nums1Size; i++) free(memo[i]);
    free(memo);
    return result;
}

using System;
using System.Collections.Generic;

public class Solution {
    private Dictionary<Tuple<int, int>, long> memo = new();
    public int MaxSum(int[] nums1, int[] nums2) {
        return (int)(Dp(nums1, nums2, 0, 0) % 1000000007);
    }

    private long Dp(int[] nums1, int[] nums2, int i, int j) {
        if (i == nums1.Length && j == nums2.Length) return 0;
        var key = Tuple.Create(i, j);
        if (memo.ContainsKey(key)) return memo[key];

        long ans = 0;
        if (i < nums1.Length) ans = Math.Max(ans, nums1[i] + Dp(nums1, nums2, i + 1, j));
        if (j < nums2.Length) ans = Math.Max(ans, nums2[j] + Dp(nums1, nums2, i, j + 1));
        if (i < nums1.Length && j < nums2.Length && nums1[i] == nums2[j])
            ans = Math.Max(ans, nums1[i] + Dp(nums1, nums2, i + 1, j + 1));

        memo[key] = ans;
        return ans;
    }
}

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.

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

TypeScript

function maxSum(nums1: number[], nums2: number[]): number {
    const mod = 1e9 + 7;
    const m = nums1.length;
    const n = nums2.length;
    let [f, g] = [0, 0];
    let [i, j] = [0, 0];
    while (i < m || j < n) {
        if (i === m) {
            g += nums2[j++];
        } else if (j === n) {
            f += nums1[i++];
        } else if (nums1[i] < nums2[j]) {
            f += nums1[i++];
        } else if (nums1[i] > nums2[j]) {
            g += nums2[j++];
        } else {
            f = g = Math.max(f, g) + nums1[i];
            i++;
            j++;
        }
    }
    return Math.max(f, g) % mod;
}

func maxSum(nums1 []int, nums2 []int) int {
	const mod int = 1e9 + 7
	m, n := len(nums1), len(nums2)
	i, j := 0, 0
	f, g := 0, 0
	for i < m || j < n {
		if i == m {
			g += nums2[j]
			j++
		} else if j == n {
			f += nums1[i]
			i++
		} else if nums1[i] < nums2[j] {
			f += nums1[i]
			i++
		} else if nums1[i] > nums2[j] {
			g += nums2[j]
			j++
		} else {
			f = max(f, g) + nums1[i]
			g = f
			i++
			j++
		}
	}
	return max(f, g) % mod
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
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	–

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

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.

Get the Maximum Score solution and explanation

The problem

Approach overview

Approach 1: Two Pointer Approach

Approach 2: Dynamic Programming with Memoization

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Get the Maximum Score solution and explanation

The problem

Approach overview

Approach 1: Two Pointer Approach

Approach 2: Dynamic Programming with Memoization

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems