Leetcode 1537. Get the Maximum Score
Problem Explanation
Given two sorted arrays of distinct integers, nums1 and nums2, we need to find out a path that gives the maximum sum of unique values from either of the arrays.
Here are the constraints:
- We can start from either of the arrays.
- We can switch to the other array at any point where both arrays contain the same value (i.e., the value of the current element is present in both arrays).
Given these conditions, we need to pick the path that maximizes the sum. Let's understand this with an example:
Suppose nums1 = [2,4,5,8,10], nums2 = [4,6,8,9] We can move on the path [2,4,6,8,10], which is formed by nums1 from index 0 to 1 and from nums2 from index 1 to last index. The sum of this path is 30, which is the maximum sum any path can have.
Solution Approach
The solution approach is a greedy one, where we keep two running sums for each array. We initialize two pointers, each pointing at the start of the two arrays.
We iterate over the arrays with these conditions:
- If the current element of nums1 is less than the current element of nums2, add it to the running sum for nums1 and move the pointer of nums1.
- If the current element of nums1 is more than nums2, add it to the running sum for nums2 and move the pointer of nums2.
- If the current elements of nums1 and nums2 are equal (which is meeting or crossing point), we add this element and the larger of the running sums of nums1 and nums2 to the answer, and reset both running sums to 0.
We do this because the crossing point is a point of choice, here we can either continue in the current array or switch to another array. And, we always want to select the array which gives us the maximal sum.
In the end, we return the final answer modulo (10^9 + 7) due to the constraint mentioned in the problem.
Python Solution
1 2python 3class Solution: 4 def maxSum(self, nums1: List[int], nums2: List[int]) -> int: 5 n1, n2 = len(nums1), len(nums2) 6 i, j, a, b, mod = 0, 0, 0, 0, 10**9+7 7 while i < n1 or j < n2: 8 if i < n1 and (j == n2 or nums1[i] < nums2[j]): 9 a += nums1[i] 10 i += 1 11 elif j < n2 and (i == n1 or nums1[i] > nums2[j]): 12 b += nums2[j] 13 j += 1 14 else: 15 # the number exists in both arrays 16 a = b = max(a, b) + nums1[i] 17 i += 1 18 j += 1 19 return max(a, b) % mod
Java Solution
1 2java 3class Solution { 4 public int maxSum(int[] nums1, int[] nums2) { 5 int i = 0, j = 0; 6 long a = 0, b = 0, mod = (long) 1e9 + 7; 7 while (i < nums1.length || j < nums2.length) { 8 if (j == nums2.length || (i < nums1.length && nums1[i] < nums2[j])) { 9 a += nums1[i++]; 10 } else if (i == nums1.length || (j < nums2.length && nums1[i] > nums2[j])) { 11 b += nums2[j++]; 12 } else { 13 // the number exists in both arrays 14 a = b = Math.max(a, b) + nums1[i]; 15 i++; j++; 16 } 17 } 18 return (int) (Math.max(a, b) % mod); 19 } 20}
JavaScript Solution
1 2javascript 3var maxSum = function(nums1, nums2) { 4 let l1 = nums1.length; 5 let l2 = nums2.length; 6 let i=0, j=0, a=0, b=0, mod=1e9+7; 7 while(i<l1 || j<l2){ 8 if(j===l2 || (i<l1 && nums1[i] < nums2[j])){ 9 a += nums1[i++]; 10 } 11 else if(i===l1 || (j<l2 && nums1[i] > nums2[j])){ 12 b += nums2[j++]; 13 } 14 else{ 15 a = b = Math.max(a, b) + nums1[i]; 16 i++; 17 j++; 18 } 19 } 20 return Math.max(a, b) % mod; 21};
C++ Solution
1 2cpp 3class Solution { 4public: 5 int maxSum(vector<int>& nums1, vector<int>& nums2) { 6 long a=0, b=0, i=0, j=0, n=nums1.size(), m=nums2.size(), mod=1e9+7; 7 while(i<n || j<m) { 8 if(j==m || (i<n && nums1[i]<nums2[j])) { 9 a += nums1[i++]; 10 } else if(i==n || (j<m && nums1[i]>nums2[j])) { 11 b += nums2[j++]; 12 } else { 13 a = b = max(a,b) + nums1[i]; 14 i++; j++; 15 } 16 } 17 return max(a, b) % mod; 18 } 19};
C# Solution
1
2c#
3public class Solution {
4 public int MaxSum(int[] nums1, int[] nums2) {
5 long i = 0, j = 0, a = 0, b = 0, mod = (long)Math.Pow(10, 9) + 7, n=nums1.Length, m=nums2.Length;
6 while(i<n || j<m) {
7 if(j==m || (i<n && nums1[i]<nums2[j])) {
8 a += nums1[i++];
9 } else if(i==n || (j<m && nums1[i]>nums2[j])) {
10 b += nums2[j++];
11 } else {
12 a = b = Math.Max(a,b) + nums1[i];
13 i++; j++;
14 }
15 }
16 return Convert.ToInt32(Math.Max(a, b) % mod);
17 }
18}
Solution Explanation
The solution starts by creating two pointers i
and j
which point to the beginning index of the two arrays. Two separate variables a
and b
are created to keep a track of running sums for both the arrays. These sums are incremented based on the comparison of the elements of the two arrays at indices i
and j
.
-
If the current element of array
nums1
is less than the current element of arraynums2
, we include the current element in the suma
and increment our pointeri
to move to the next element in arraynums1
. -
If the current element of array
nums1
is greater than the current element of arraynums2
, we include the current element in sumb
and increment the pointerj
to move to the next element in arraynums2
. -
Now, if the current elements of both arrays are equal, this serves as a crossing point, i.e., we can either continue on the current array or switch to the other one. Being a greedy solution, we aim to maximize the sum. So, we add to our total sum
a
orb
(whichever is greater) and the current element (since it's common in both arrays) and set botha
andb
to this value. This effectively includes the path with greater sum till the crossing point in the total sum.
This process continues until we have traversed both arrays completely.
After traversing both arrays, to get the final sum, we take the maximum of a
and b
. This is because either a
or b
will contain the sum of our path. We return this final sum modulo (10^9 + 7) as mentioned in the problem.
Conclusion
This problem demonstrates a classic greedy algorithm where we always aim to make a locally optimal choice at each step with the hope that these local optimums will lead us to the globally optimal solution. The problem makes great use of this insight by moving along the paths and switching arrays at appropriate intervals to maximize the sum.
In terms of time complexity, since we traverse each of the two arrays once, the solution is linear, i.e., O(n), where n is the sum of the lengths of the two input arrays.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.