Leetcode 1537. Get the Maximum Score

Problem Explanation

Given two sorted arrays of distinct integers, nums1 and nums2, we need to find out a path that gives the maximum sum of unique values from either of the arrays.

Here are the constraints:

• We can start from either of the arrays.
• We can switch to the other array at any point where both arrays contain the same value (i.e., the value of the current element is present in both arrays).

Given these conditions, we need to pick the path that maximizes the sum. Let's understand this with an example:

Suppose nums1 = [2,4,5,8,10], nums2 = [4,6,8,9] We can move on the path [2,4,6,8,10], which is formed by nums1 from index 0 to 1 and from nums2 from index 1 to last index. The sum of this path is 30, which is the maximum sum any path can have.

Solution Approach

The solution approach is a greedy one, where we keep two running sums for each array. We initialize two pointers, each pointing at the start of the two arrays.

We iterate over the arrays with these conditions:

• If the current element of nums1 is less than the current element of nums2, add it to the running sum for nums1 and move the pointer of nums1.
• If the current element of nums1 is more than nums2, add it to the running sum for nums2 and move the pointer of nums2.
• If the current elements of nums1 and nums2 are equal (which is meeting or crossing point), we add this element and the larger of the running sums of nums1 and nums2 to the answer, and reset both running sums to 0.

We do this because the crossing point is a point of choice, here we can either continue in the current array or switch to another array. And, we always want to select the array which gives us the maximal sum.

In the end, we return the final answer modulo (10^9 + 7) due to the constraint mentioned in the problem.

Python Solution

1
2python
3class Solution:
4    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
5        n1, n2 = len(nums1), len(nums2)
6        i, j, a, b, mod = 0, 0, 0, 0, 10**9+7
7        while i < n1 or j < n2:
8            if i < n1 and (j == n2 or nums1[i] < nums2[j]):
9                a += nums1[i]
10                i += 1
11            elif j < n2 and (i == n1 or nums1[i] > nums2[j]):
12                b += nums2[j]
13                j += 1
14            else:  
15                # the number exists in both arrays
16                a = b = max(a, b) + nums1[i]
17                i += 1
18                j += 1
19        return max(a, b) % mod

Java Solution

1
2java
3class Solution {
4    public int maxSum(int[] nums1, int[] nums2) {
5        int i = 0, j = 0;
6        long a = 0, b = 0, mod = (long) 1e9 + 7;
7        while (i < nums1.length || j < nums2.length) {
8            if (j == nums2.length || (i < nums1.length && nums1[i] < nums2[j])) {
9                a += nums1[i++];
10            } else if (i == nums1.length || (j < nums2.length && nums1[i] > nums2[j])) {
11                b += nums2[j++];
12            } else { 
13                // the number exists in both arrays 
14                a = b = Math.max(a, b) + nums1[i];
15                i++; j++;
16            }
17        }
18        return (int) (Math.max(a, b) % mod);
19    }
20}

JavaScript Solution

1
2javascript
3var maxSum = function(nums1, nums2) {
4    let l1 = nums1.length;
5    let l2 = nums2.length;
6    let i=0, j=0, a=0, b=0, mod=1e9+7;
7    while(i<l1 || j<l2){
8        if(j===l2 || (i<l1 && nums1[i] < nums2[j])){
9            a += nums1[i++];
10        }
11        else if(i===l1 || (j<l2 && nums1[i] > nums2[j])){
12            b += nums2[j++];
13        }
14        else{
15            a = b = Math.max(a, b) + nums1[i];
16            i++;
17            j++;
18        }
19    }
20    return Math.max(a, b) % mod;
21};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int maxSum(vector<int>& nums1, vector<int>& nums2) {
6        long a=0, b=0, i=0, j=0, n=nums1.size(), m=nums2.size(), mod=1e9+7;
7        while(i<n || j<m) {
8            if(j==m || (i<n && nums1[i]<nums2[j])) {
9                a += nums1[i++];
10            } else if(i==n || (j<m && nums1[i]>nums2[j])) {
11                b += nums2[j++];
12            } else {
13                a = b = max(a,b) + nums1[i];
14                i++; j++;
15            }
16        }
17        return max(a, b) % mod;
18    }
19};

C# Solution

1
2c#
3public class Solution {
4    public int MaxSum(int[] nums1, int[] nums2) {
5        long i = 0, j = 0, a = 0, b = 0, mod = (long)Math.Pow(10, 9) + 7, n=nums1.Length, m=nums2.Length;
6        while(i<n || j<m) {
7            if(j==m || (i<n && nums1[i]<nums2[j])) {
8                a += nums1[i++];
9            } else if(i==n || (j<m && nums1[i]>nums2[j])) {
10                b += nums2[j++];
11            } else {
12                a = b = Math.Max(a,b) + nums1[i];
13                i++; j++;
14            }
15        }
16        return Convert.ToInt32(Math.Max(a, b) % mod);
17    }
18}

Solution Explanation

The solution starts by creating two pointers i and j which point to the beginning index of the two arrays. Two separate variables a and b are created to keep a track of running sums for both the arrays. These sums are incremented based on the comparison of the elements of the two arrays at indices i and j.

1. If the current element of array nums1 is less than the current element of array nums2, we include the current element in the sum a and increment our pointer i to move to the next element in array nums1.

2. If the current element of array nums1 is greater than the current element of array nums2, we include the current element in sum b and increment the pointer j to move to the next element in array nums2.

3. Now, if the current elements of both arrays are equal, this serves as a crossing point, i.e., we can either continue on the current array or switch to the other one. Being a greedy solution, we aim to maximize the sum. So, we add to our total sum a or b (whichever is greater) and the current element (since it's common in both arrays) and set both a and b to this value. This effectively includes the path with greater sum till the crossing point in the total sum.

This process continues until we have traversed both arrays completely.

After traversing both arrays, to get the final sum, we take the maximum of a and b. This is because either a or b will contain the sum of our path. We return this final sum modulo (10^9 + 7) as mentioned in the problem.

Conclusion

This problem demonstrates a classic greedy algorithm where we always aim to make a locally optimal choice at each step with the hope that these local optimums will lead us to the globally optimal solution. The problem makes great use of this insight by moving along the paths and switching arrays at appropriate intervals to maximize the sum.

In terms of time complexity, since we traverse each of the two arrays once, the solution is linear, i.e., O(n), where n is the sum of the lengths of the two input arrays.