1537. Max Score

Get the Maximum Score

A great problem for training two pointers.

Key insight: whenever two sorted arrays share a common value,

that value becomes an interchange. For what?

We can choose to switch our traversal path from one array to the other.

However, this switch is optional. Only switch if doing so gives a better score.

🗝️🔒 Two Pointers' Push & Pull

Each array has its own pointer 🪡.

As long as both idxOne and idxTwo don't go past the end of their respective arrays,

and their pointed values are not equal yet,

just keep incrementing the pointer having a smaller value,

until its pointed value $\geq$ the other pointer's value.

BTW: before incrementing, that pointed value must add into its pointer's corresponding score.

👩🏻‍❤️‍💋‍👨🏻 When the Couple Finally Agree

Once both pointers point to the same value,

directly compare scoreOne and scoreTwo,

and add max(scoreOne, scoreTwo) + nums[scoreTwo] to maxScore.

Why add nums[scoreTwo] as well? Remember:

the pointed value of a pointer is added to its score right before incrementing,

so our common value nums[scoreTwo] hasn't been counted yet.

Once maxScore absorbs max(scoreOne, scoreTwo) + nums[scoreTwo],

both pointers advance by one step, while scoreOne and scoreTwo reset to 0.

Someone Always Has to Clean Up

Just like the merge phase of that good old merge sort,

one array will always be finished first,

while the other still has unvisited values. The same happens here, too.

There must be exactly one pointer that hasn't scanned all values in its array,

so we need to keep incrementing it and adding values to its score.

Finally, add max(scoreOne, scoreTwo) into maxScore, and return maxScore.

Again, as asked: accumulated values can grow astronomically large,

we have to apply $10^9 + 7$ as modulo to control the size of maxScore.

Our whole algorithm creates two pointers, three score variables, and one modulo constant.

6 variables needed in total, so space complexity is $O(1)$.

Time complexity is clearly $O(|\text{nums1}| + |\text{nums2}|)$. Each value is scanned only once.

C++

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

int findMaxScore(vector<int>& nums1, vector<int>& nums2) { // LeetCode Q.1537.
    long long maxScore = 0; // Must use long long to prevent overflow.
    long long scoreOne = 0, scoreTwo = 0;

    int modulo = pow(10, 9) + 7;

    int idxOne = 0, idxTwo = 0;

    while (idxOne < nums1.size() && idxTwo < nums2.size()) {
        while (idxOne < nums1.size() && nums1[idxOne] < nums2[idxTwo]) {
            scoreOne += nums1[idxOne];
            idxOne++;
        }
        if (idxOne == nums1.size()) break; // Array 1 can't catch up.

        while (idxTwo < nums2.size() && nums2[idxTwo] < nums1[idxOne]) {
            scoreTwo += nums2[idxTwo];
            idxTwo++;
        }
        if (idxTwo == nums2.size()) break; // Array 2 can't catch up.

        if (nums1[idxOne] == nums2[idxTwo]) { // Arrays can now compare scores.
            scoreOne += nums1[idxOne];
            scoreTwo += nums2[idxTwo];

            maxScore += max(scoreOne, scoreTwo);
            if (maxScore > modulo) maxScore %= modulo; // Control size.

            scoreOne = 0, scoreTwo = 0; // Reset for next while iteration.
            idxOne++;
            idxTwo++;
        }
    }

    while (idxOne < nums1.size()) { // Remaining nums from array 1.
        scoreOne += nums1[idxOne];
        idxOne++;
    }

    while (idxTwo < nums2.size()) { // Remaining nums from array 2.
        scoreTwo += nums2[idxTwo];
        idxTwo++;
    }

    maxScore += max(scoreOne, scoreTwo);
    return maxScore % modulo; // Control size.
}

Python

def find_max_score(nums_1: list[int], nums_2: list[int]) -> int:  # LeetCode Q.1537.
    max_score = 0
    modulo = 10 ** 9 + 7

    score_1, score_2 = 0, 0

    idx_1, idx_2 = 0, 0

    while idx_1 < len(nums_1) and idx_2 < len(nums_2):
        while idx_1 < len(nums_1) and nums_1[idx_1] < nums_2[idx_2]:
            score_1 += nums_1[idx_1]
            idx_1 += 1
        
        if idx_1 == len(nums_1): break  # Array 1 can't catch up.

        while idx_2 < len(nums_2) and nums_2[idx_2] < nums_1[idx_1]:
            score_2 += nums_2[idx_2]
            idx_2 += 1
        
        if idx_2 == len(nums_2): break  # Array 2 can't catch up.

        if nums_1[idx_1] == nums_2[idx_2]:  # Arrays can now compare scores.
            score_1 += nums_1[idx_1]
            score_2 += nums_2[idx_2]

            max_score += max(score_1, score_2)
            if max_score > modulo: max_score %= modulo  # Control size.
            
            score_1, score_2 = 0, 0  # Reset for next while iteration.
            idx_1 += 1
            idx_2 += 1

    while idx_1 < len(nums_1):  # Remaining nums from array 1.
        score_1 += nums_1[idx_1]
        idx_1 += 1

    while idx_2 < len(nums_2):  # Remaining nums from array 2.
        score_2 += nums_2[idx_2]
        idx_2 += 1

    max_score += max(score_1, score_2)
    return max_score % modulo  # Control size.