You are given two sorted arrays of distinct integers
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
nums2you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path). 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.
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].
When I was faced with this question, I tried DFS and adding memorization which converts it into a top-down dynamic programming approach, but ended up with
RecursionError: maximum recursion depth exceeded. Finally it became another time to learn from @lee215.
Using two pointers, we can solve it with one pass. O(n) time complexity and O(1) space complexity.
The reason DFS/DF wouldn’t work is they don’t utilize the condition that the two input arrays are actually sorted. We can initialize two pointers
j pointing to
nums2 accordingly. Each time we would move the smaller one comparing nums1[i] and nums2[j], and record the accumulative sum. When they are equal, we would pick the largest one and move them together.
class Solution: def maxSum(self, nums1: List[int], nums2: List[int]) -> int: i = j = 0 a = b = 0 l1,l2 = len(nums1),len(nums2) while i < l1 or j < l2: if i < l1 and (j==l2 or nums1[i]<nums2[j]): a += nums1[i] i += 1 elif j < l2 and (i==l1 or nums1[i]>nums2[j]): b += nums2[j] j += 1 else: a = b = max(a,b) + nums1[i] i += 1 j += 1 return max(a,b) % (10**9+7)