Hex.*

LC1537 - Get the Maximum Score

Posted on In
Leetcode: 138/2658 (57+66+15)

Description

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 uniques 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 10^9 + 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.

Solutions

Definition: “fork” – encountered a value that exists in both nums1 and nums2

  • Use two pointers i, j to traverse the arrays nums1 and nums2 from the beginning, respectively, the current sum is recorded as sum1, sum2
  • In order for the two pointers to meet at the fork, we take advantage of the ordering of the array and move the pointer with the smaller value forward one step at a time.
  • At the fork, we assign sum1 and sum2 to the larger of the two (greedy), plus the value of the current fork, so that both pointers move forward (it can be understood that this fork is the new starting point) , and update the base value to the larger sum of the previous two paths, and start again).
  • Repeat this cycle until a path comes to an end.
  • Two paths, one of which may not be completed, so we add the remaining numbers in the array to it.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# O(n) time | O(1) space
class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        i, j, sum1, sum2 = 0, 0, 0, 0
        mod = 1000000007
        len1 = len(nums1)
        len2 = len(nums2)
        
        while i < len1 and j < len2:
            num1 = nums1[i]
            num2 = nums2[j]
            if num1 < num2:
                sum1 += num1
                i+=1
            elif num1 > num2:
                sum2 += num2
                j+=1
            else:
                sum1 = sum2 = (max(sum1, sum2) + num1) % mod
                i+=1
                j+=1
        if i < len1:
            sum1+=sum(nums1[i:])
        if j < len2:
            sum2+=sum(nums2[j:])
        return max(sum1, sum2)%mod

Note

In most programming competitions, we are required to answer the result in 10^9+7 modulo. The reason behind this is, if problem constraints are large integers, only efficient algorithms can solve them in an allowed limited time.

1
2
mod = 1000000007
mod = int(math.pow(10,9)+7)