Max sum path in two arrays

JavaView on GFG

Time: O(n+m)

Space: O(1)

Problem Overview

Two sorted arrays with common elements.

See our study guide for structured GFG and LeetCode practice.

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?