Get the Maximum Score - Two Pointers / Advanced

Problems
1

https://algo.monster/problems/get_maximum_score

2

It would be nice to have a lesson explaining a little more about modulo. For example, explaining the meaning of “modded by 10^9 + 7”. Thanks.

3

Why is modulo before the end result needed in Python?

4

It’s just the return value could be very big (greater than 2^31) that will cause overflow.

5

Since the result might be very large and cause overflow, return the maximum score modded by 10^9 + 7.

6

Looking at test case #2, shouldn’t the answer to that be 27? How does one get 28 for that case?

7

def maxSum(arr1, arr2):
i, j, m, n = 0, 0, len(arr1), len(arr2)
curNums1Sum, curNums2Sum = 0, 0

while i < m and j < n:
    # Find the smaller number for each array where the pointer is and add it to their respective curNumsSum
    if arr1[i] < arr2[j]:
        curNums1Sum += arr1[i]
        i += 1
    elif arr1[i] > arr2[j]:
        curNums2Sum += arr2[j]
        j += 1
    else:
        # Both pointers are pointing to the "Teleporter number" (Same number). arr1[i] == arr2[j]
        # Find the curMaxSum and add the "Teleporter number" (Can be either arr1[i] or arr2[j])
        # Set the curNums1Sum and curNums1Sum to be curMaxSum
        curNums1Sum = curNums2Sum = max(curNums1Sum, curNums2Sum) + arr1[i]
        i += 1
        j += 1
# Add the last numbers (if there is any) to the curNumsSum once any of the pointers reach the end (while loop ends)
curNums1Sum += sum(arr1[i:])
curNums2Sum += sum(arr2[j:])

return max(curNums1Sum, curNums2Sum) % (10**9 + 7)
8

It isn’t strictly needed since Python supports BigInt natively but it is an easy way to uniformize the answers (and tests) between languages.

9

in c++ solution line 25 do nothing:
result % MODULO_AMT;
should be “result =% MODULO_AMT;” i think

10

Clean Java Solution

        int m = nums1.size(), n = nums2.size();
        long scores1 = 0, scores2 = 0;
        int i = 0, j = 0;

        while (i < m && j < n) {
            if (nums1.get(i) < nums2.get(j)) scores1 += nums1.get(i++);
            else if (nums1.get(i) > nums2.get(j)) scores2 += nums2.get(j++);
            else {
                scores1 = scores2 = Math.max(scores1 + nums1.get(i++), scores2 + nums2.get(j++));
            }
        }

        while (i < m) scores1 += nums1.get(i++);
        while (j < n) scores2 += nums2.get(j++);

        return (int) (Math.max(scores1, scores2) % (1e9 + 7));
11

you treat this problem as a tree

private static class Node
{
int val;
Node left;
Node right;
public Node(int val) {
this.val = val;
}
}
public static int maximumScore(List arr1, List arr2) {
Map<Integer, Node> map = buildTreeMap(arr1, arr2);

   long result = Math.max(maxScore(map.get(arr1.get(0))), maxScore(map.get(arr2.get(0)))) ;
    
   return (int)(result % (Math.pow(10, 9) + 7));
}


private static long maxScore(Node node) {
    if (node == null) 
        return 0;
    
    return node.val + Math.max(maxScore(node.left), maxScore(node.right));
    
}

private static Map<Integer, Node> buildTreeMap(List<Integer> arr1, List<Integer> arr2) {
    Map<Integer, Node> map = new HashMap<>(); 

    // build map from all values in arr1 + arr2
    for(int num: arr1) {
       map.put(num, new Node(num));
    }

    for(int num: arr2) {
       map.put(num, new Node(num));
    }

    // link nodes from arr1 to the right
    for(int i = 1; i < arr1.size(); i++) {
       map.get(arr1.get(i - 1)).right = map.get(arr1.get(i));
    }

    // link nodes from arr2 to the left
    for(int i = 1; i < arr2.size(); i++) {
       map.get(arr2.get(i - 1)).left = map.get(arr2.get(i));
    }
     
    return map;
 }
12

What is the corresponding leetcode question to this? I want to increase medium/hard count :slight_smile: