Given two sorted arrays of distinct integers arr1 and arr2. Each array may have some elements in common with the other array. Find the maximum sum of a path from the beginning of any array to the end of any array. You can switch from one array to another array only at the common elements.
Note: When we switch from one array to other, we need to consider the common element only once in the result.
Examples :
Input: arr1 = [2, 3, 7, 10, 12] , arr2 = [1, 5, 7, 8] Output: 35 Explanation: The path will be 1+5+7+10+12 = 35, where 1 and 5 come from arr2 and then 7 is common so we switch to arr1 and add 10 and 12.
Input: arr1 = [1, 2, 3] , arr2[] = [3, 4, 5] Output: 15 Explanation: The path will be 1+2+3+4+5=15.
Expected Time Complexity: O(m + n)
Expected Auxiliary Space: O(1)
Constraints:
1 <= arr1.size(), arr2.size() <= 104
1 <= arr1[i], arr2[i] <= 105
Approach 01:
-
C++
-
Python
class Solution { public: int maxPathSum(vector<int> &arr1, vector<int> &arr2) { int index1 = 0, index2 = 0; int size1 = arr1.size(), size2 = arr2.size(); int sum1 = 0, sum2 = 0; int result = 0; // Traverse both arrays while (index1 < size1 && index2 < size2) { if (arr1[index1] < arr2[index2]) { sum1 += arr1[index1++]; } else if (arr1[index1] > arr2[index2]) { sum2 += arr2[index2++]; } else { // Add the maximum of sum1 and sum2 to the result result += max(sum1, sum2) + arr1[index1]; sum1 = 0; sum2 = 0; index1++; index2++; } } // Add remaining elements from arr1 while (index1 < size1) { sum1 += arr1[index1++]; } // Add remaining elements from arr2 while (index2 < size2) { sum2 += arr2[index2++]; } // Add the maximum of remaining sums result += max(sum1, sum2); return result; } };
from typing import List class Solution: def maxPathSum(self, arr1: List[int], arr2: List[int]) -> int: index1, index2 = 0, 0 size1, size2 = len(arr1), len(arr2) sum1, sum2 = 0, 0 result = 0 # Traverse both arrays while index1 < size1 and index2 < size2: if arr1[index1] < arr2[index2]: sum1 += arr1[index1] index1 += 1 elif arr1[index1] > arr2[index2]: sum2 += arr2[index2] index2 += 1 else: # Add the maximum of sum1 and sum2 to the result result += max(sum1, sum2) + arr1[index1] sum1, sum2 = 0, 0 index1 += 1 index2 += 1 # Add remaining elements from arr1 while index1 < size1: sum1 += arr1[index1] index1 += 1 # Add remaining elements from arr2 while index2 < size2: sum2 += arr2[index2] index2 += 1 # Add the maximum of remaining sums result += max(sum1, sum2) return result
Time Complexity
- Traversing Both Arrays:
The algorithm uses a single loop to traverse both arrays
arr1
andarr2
. Each element of both arrays is processed exactly once, so the time complexity of this step is \( O(n + m) \), where \( n \) is the size ofarr1
and \( m \) is the size ofarr2
. - Overall Time Complexity:
The overall time complexity is \( O(n + m) \) since this is the dominating term in the algorithm’s execution.
Space Complexity
- Additional Variables:
The solution uses a few integer variables (
index1
,index2
,sum1
,sum2
, andresult
) to keep track of indices and cumulative sums. These consume \( O(1) \) space. - Overall Space Complexity:
Since the algorithm only uses a constant amount of extra space, the overall space complexity is \( O(1) \).