Max sum path in two arrays

JavaView on GFG

Time: O(n+m)

Space: O(1)

Intuition

Two sorted arrays with common elements. Find path (switch between arrays at common elements) with maximum sum.

Algorithm

1Two pointers. Accumulate sums between common elements. At each common element: take max of both accumulated sums, add common element value.

Common Pitfalls

•O(m+n) merge-like scan. Key insight: switch paths only at common elements when it is beneficial.

Max sum path in two arrays.java

Java

// Approach: Two-pointer merge. Accumulate sums; at common elements take maximum of both paths.
// Time: O(n+m) Space: O(1)
import java.util.*;

class Solution {
    public int maxPathSum(List<Integer> arr1, List<Integer> arr2) {
        int i = 0, j = 0, sum1 = 0, sum2 = 0, total = 0;
        while (i < arr1.size() && j < arr2.size()) {
            if (arr1.get(i) < arr2.get(j))
                sum1 += arr1.get(i++);
            else if (arr2.get(j) < arr1.get(i))
                sum2 += arr2.get(j++);
            else {
                total += Math.max(sum1, sum2) + arr1.get(i);
                sum1 = 0;
                sum2 = 0;
                i++;
                j++;
            }
        }
        while (i < arr1.size())
            sum1 += arr1.get(i++);
        while (j < arr2.size())
            sum2 += arr2.get(j++);
        return total + Math.max(sum1, sum2);
    }
}

Was this solution helpful?