Max sum path in two arrays

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() <= 10⁴
1 <= arr1[i], arr2[i] <= 10⁵

Approach 01:

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 and arr2. 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 of arr1 and \( m \) is the size of arr2.

• 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, and result) 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) \).