1537. Get the Maximum Score LeetCode Solution

In this guide, you will get 1537. Get the Maximum Score LeetCode Solution with the best time and space complexity. The solution to Get the Maximum Score problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Get the Maximum Score solution in C++
Get the Maximum Score solution in Java
Get the Maximum Score solution in Python
Additional Resources

1537. Get the Maximum Score LeetCode Solution image

Problem Statement of Get the Maximum Score

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 109 + 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 <= 105
1 <= nums1[i], nums2[i] <= 107
nums1 and nums2 are strictly increasing.

Complexity Analysis

Time Complexity: O(|\texttt{nums1}| + |\texttt{nums2}|)
Space Complexity: O(1)

1537. Get the Maximum Score LeetCode Solution in C++

class Solution {
 public:
  int maxSum(vector<int>& nums1, vector<int>& nums2) {
    constexpr int kMod = 1'000'000'007;
    // Keep the running the sum of `nums1` and `nums2` before the next
    // rendezvous. Since `nums1` and `nums2` are increasing, move forward on the
    // smaller one to ensure we don't miss any rendezvous. When meet rendezvous,
    // choose the better path.
    long ans = 0;
    // sum(nums1) in (the prevoious rendezvous, the next rendezvous)
    long sum1 = 0;
    // sum(nums2) in (the prevoious rendezvous, the next rendezvous)
    long sum2 = 0;
    int i = 0;  // nums1's index
    int j = 0;  // nums2's index

    while (i < nums1.size() && j < nums2.size())
      if (nums1[i] < nums2[j]) {
        sum1 += nums1[i++];
      } else if (nums1[i] > nums2[j]) {
        sum2 += nums2[j++];
      } else {  // An rendezvous happens.
        ans += max(sum1, sum2) + nums1[i];
        sum1 = 0;
        sum2 = 0;
        ++i;
        ++j;
      }

    while (i < nums1.size())
      sum1 += nums1[i++];

    while (j < nums2.size())
      sum2 += nums2[j++];

    return (ans + max(sum1, sum2)) % kMod;
  }
};
/* code provided by PROGIEZ */

1537. Get the Maximum Score LeetCode Solution in Java

class Solution {
  public int maxSum(int[] nums1, int[] nums2) {
    final int kMod = 1_000_000_007;
    // Keep the running the sum of `nums1` and `nums2` before the next rendezvous.
    // Since `nums1` and `nums2` are increasing, move forward on the smaller one
    // to ensure we don't miss any rendezvous. When meet rendezvous, choose the
    // better path.
    long ans = 0;
    // sum(nums1) in (the prevoious rendezvous, the next rendezvous)
    long sum1 = 0;
    // sum(nums2) in (the prevoious rendezvous, the next rendezvous)
    int i = 0; // nums1's index
    int j = 0; // nums2's index

    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 { // An rendezvous happens.
        ans += Math.max(sum1, sum2) + nums1[i];
        sum1 = 0;
        sum2 = 0;
        ++i;
        ++j;
      }

    while (i < nums1.length)
      sum1 += nums1[i++];

    while (j < nums2.length)
      sum2 += nums2[j++];

    return (int) ((ans + Math.max(sum1, sum2)) % kMod);
  }
}
// code provided by PROGIEZ

1537. Get the Maximum Score LeetCode Solution in Python

class Solution:
  def maxSum(self, nums1: list[int], nums2: list[int]) -> int:
    # Keep the running the sum of `nums1` and `nums2` before the next rendezvous.
    # Since `nums1` and `nums2` are increasing, move forward on the smaller one
    # to ensure we don't miss any rendezvous. When meet rendezvous, choose the
    # better path.
    ans = 0
    sum1 = 0  # sum(nums1) in (the prevoious rendezvous, the next rendezvous)
    sum2 = 0  # sum(nums2) in (the prevoious rendezvous, the next rendezvous)
    i = 0  # nums1's index
    j = 0  # nums2's index

    while i < len(nums1) and j < len(nums2):
      if nums1[i] < nums2[j]:
        sum1 += nums1[i]
        i += 1
      elif nums1[i] > nums2[j]:
        sum2 += nums2[j]
        j += 1
      else:  # An rendezvous happens.
        ans += max(sum1, sum2) + nums1[i]
        sum1 = 0
        sum2 = 0
        i += 1
        j += 1

    while i < len(nums1):
      sum1 += nums1[i]
      i += 1

    while j < len(nums2):
      sum2 += nums2[j]
      j += 1

    return (ans + max(sum1, sum2)) % (10**9 + 7)
 # code by PROGIEZ