Get the Maximum Score - Practice Coding Problems

Get the Maximum Score - Problem

Path Navigation with Maximum Score

You are given two sorted arrays of distinct integers nums1 and nums2. Your goal is to find a path through these arrays that maximizes the sum of values you collect.

🛣️ Path Rules:

Start at index 0 of either array
Move left-to-right within your current array
When you encounter a value that exists in both arrays, you can switch paths
Each unique value is counted only once in your score

Example: If nums1 = [2,4,5,8,10] and nums2 = [4,6,8,9], you could take path: 2 → 4 → 6 → 8 → 9 for score = 29, or 2 → 4 → 5 → 8 → 10 for score = 29.

Return the maximum possible score modulo 10⁹ + 7.

Input & Output

example_1.py — Basic Path Selection

$ Input: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]

› Output: 30

💡 Note: Optimal path: 2 → 4 → 6 → 8 → 10. At intersection 4, both paths have equal sum (2 vs 0), so we can choose either. At intersection 8, path through nums2 gives us 4+6=10 vs nums1's 4+5=9, so we switch to nums2, then continue to get the maximum ending.

example_2.py — Multiple Intersections

$ Input: nums1 = [1,3,5,7,9], nums2 = [3,5,100]

› Output: 109

💡 Note: Optimal path: 1 → 3 → 5 → 100. Start with nums1 to get 1, then at intersection 3, nums1 path has sum 1 vs nums2's 0, so continue on nums1. At intersection 5, both have equal recent sums, but we can switch to nums2 to get the large value 100.

example_3.py — No Intersections

$ Input: nums1 = [1,4,5,8,9], nums2 = [2,3,6,7]

› Output: 35

💡 Note: Since there are no common elements, we must choose one complete array. nums1 sum = 27, nums2 sum = 18, so we choose nums1 entirely. Wait, that's wrong calculation. nums1=27, nums2=18, but we need to take the path that gives us maximum, which could involve taking some from each. Actually, with no intersections, we take the array with larger sum: nums1 = 1+4+5+8+9 = 27.

Constraints

1 ≤ nums1.length, nums2.length ≤ 10⁵
1 ≤ nums1[i], nums2[i] ≤ 10⁷
nums1 and nums2 are strictly increasing
All elements in each array are distinct

Visualization

Tap to expand

Understanding the Visualization

Start Journey

Begin on either highway, tracking toll collections separately

Collect Tolls

As you drive, accumulate tolls from your current highway

Bridge Decision

At each bridge, compare total tolls and switch to the better highway

Reset & Continue

After switching, reset toll counters and continue the journey

Final Choice

At journey's end, add the better of the two remaining highway segments

Key Takeaway

🎯 Key Insight: At each intersection, greedily choose the path segment with higher accumulated value. This works because sorted arrays ensure no future intersection will be missed, and past optimal choices remain optimal.

Asked in

G Google 42 a Amazon 38 f Meta 31 ⊞ Microsoft 25

The optimal solution uses two pointers to traverse both sorted arrays simultaneously. At each intersection point (common element), we greedily choose the path segment with the higher cumulative sum. This works because the arrays are sorted, and past decisions don't affect future optimal choices. The algorithm runs in O(n+m) time with O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Path Exploration	O(2^k)	O(k)	Recursively explore all possible paths with memoization
Two Pointers (Optimal)	O(n + m)	O(1)	Use two pointers to traverse both arrays simultaneously, making optimal choices at intersections

Recursive Path Exploration — Algorithm Steps

Find all intersection points (common elements) between arrays
For each intersection, recursively explore both path choices
Calculate sum for each complete path
Return maximum sum found across all paths

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with both arrays and two possible starting paths

First Intersection

At common element 4, branch into two recursive calls

Recursive Branching

Each intersection creates exponential branches

Path Completion

Base case reached, return path sum

Code -

solution.c — C

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

#define MOD 1000000007
#define max(a,b) ((a) > (b) ? (a) : (b))

int findIndex(int* arr, int size, int target, int start) {
    for (int i = start; i < size; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

long long solve(int* nums1, int size1, int* nums2, int size2, int i1, int i2, int onFirst) {
    if (i1 >= size1 && i2 >= size2) {
        return 0;
    }
    
    if (onFirst) {
        if (i1 >= size1) {
            return solve(nums1, size1, nums2, size2, i1, i2, 0);
        }
        
        int val = nums1[i1];
        int j = findIndex(nums2, size2, val, i2);
        
        if (j != -1) {
            long long stay = val + solve(nums1, size1, nums2, size2, i1 + 1, j + 1, 1);
            long long switch_ = val + solve(nums1, size1, nums2, size2, i1 + 1, j + 1, 0);
            return max(stay, switch_) % MOD;
        } else {
            return (val + solve(nums1, size1, nums2, size2, i1 + 1, i2, 1)) % MOD;
        }
    } else {
        if (i2 >= size2) {
            return solve(nums1, size1, nums2, size2, i1, i2, 1);
        }
        
        int val = nums2[i2];
        int j = findIndex(nums1, size1, val, i1);
        
        if (j != -1) {
            long long switch_ = val + solve(nums1, size1, nums2, size2, j + 1, i2 + 1, 1);
            long long stay = val + solve(nums1, size1, nums2, size2, j + 1, i2 + 1, 0);
            return max(stay, switch_) % MOD;
        } else {
            return (val + solve(nums1, size1, nums2, size2, i1, i2 + 1, 0)) % MOD;
        }
    }
}

int maxSum(int* nums1, int size1, int* nums2, int size2) {
    return max(solve(nums1, size1, nums2, size2, 0, 0, 1),
              solve(nums1, size1, nums2, size2, 0, 0, 0));
}

int main() {
    int nums1[] = {2, 4, 5, 8, 10};
    int nums2[] = {4, 6, 8, 9};
    printf("%d\n", maxSum(nums1, 5, nums2, 4));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^k)

Where k is the number of common elements. Each intersection creates 2 choices, leading to exponential paths

✓ Linear Growth

Space Complexity

O(k)

Recursion depth is bounded by number of intersection points

✓ Linear Space

41.2K Views

High Frequency

~25 min Avg. Time

1.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Path Exploration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler