Problem Statement

You are given two sorted arrays containing distinct integers. Some elements may be common in both arrays.

You start from the beginning of either array and move towards the end. At any common element, you are allowed to switch from one array to the other.

Your goal is to find the maximum possible sum of all visited elements.

Important: If you switch at a common element, count that element only once.

Example

Input

Code
a = [2, 3, 7, 10, 12]
b = [1, 5, 7, 8]

Output

Code
35

Explanation

Possible path:

Code
1 → 5 → 7 → 10 → 12

Sum:

Code
1 + 5 + 7 + 10 + 12 = 35

We start in array b, then switch to array a at the common element 7.

Observation

Since both arrays are sorted, we can traverse them using two pointers.

Before reaching a common element, we have two possible paths:

At every common element, we simply choose the path having the larger accumulated sum.

Approach

Maintain:

Traverse both arrays simultaneously.

Case 1

If:

Code
a[i] < b[j]

Add the element to sum1.

Case 2

If:

Code
a[i] > b[j]

Add the element to sum2.

Case 3

If:

Code
a[i] == b[j]

A common element is found.

Now we have two paths:

Code
Previous Common
       |
   sum1 path

Previous Common
       |
   sum2 path

Take the better one.

Java
ans += Math.max(sum1, sum2);

Now add the common element only once.

Java
ans += a[i];

Reset both sums because we are starting a new segment.

After traversal finishes, one array may still contain elements.

Add the remaining elements to their respective sums.

Finally:

Java
ans += Math.max(sum1, sum2);

Dry Run

Input

Code
a = [2,3,7,10,12]
b = [1,5,7,8]

Initially

Code
sum1 = 0
sum2 = 0
ans = 0

Step 1

Code
2 > 1
Code
sum2 = 1

Step 2

Code
2 < 5
Code
sum1 = 2

Step 3

Code
3 < 5
Code
sum1 = 5

Step 4

Common element:

Code
7 == 7

Current sums:

Code
sum1 = 5
sum2 = 6

Choose maximum:

Code
ans = 6 + 7 = 13

Reset:

Code
sum1 = 0
sum2 = 0

Continue

Remaining:

Code
a : 10 12
b : 8
Code
sum1 = 22
sum2 = 8

Take larger:

Code
ans += 22

Final Answer

Code
13 + 22 = 35

Code

Java
class Solution {
    public int maxPathSum(int[] a, int[] b) {

        int i = 0;
        int j = 0;

        int sum1 = 0;
        int sum2 = 0;

        int ans = 0;

        while (i < a.length && j < b.length) {

            if (a[i] < b[j]) {

                sum1 += a[i];
                i++;

            } else if (a[i] > b[j]) {

                sum2 += b[j];
                j++;

            } else {

                ans += Math.max(sum1, sum2) + a[i];

                sum1 = 0;
                sum2 = 0;

                i++;
                j++;
            }
        }

        while (i < a.length) {
            sum1 += a[i];
            i++;
        }

        while (j < b.length) {
            sum2 += b[j];
            j++;
        }

        ans += Math.max(sum1, sum2);

        return ans;
    }
}

Code Explanation (Line by Line)

Initialize Pointers

Java
int i = 0;
int j = 0;

Running Sums

Java
int sum1 = 0;
int sum2 = 0;

These store the sum collected since the last common element.

Final Answer

Java
int ans = 0;

Stores the maximum path sum.

Traverse Both Arrays

Java
while(i < a.length && j < b.length)

Continue until one array finishes.

When Element in a Is Smaller

Java
sum1 += a[i];
i++;

We cannot switch yet because there is no common element.

So continue collecting the sum in array a.

When Element in b Is Smaller

Java
sum2 += b[j];
j++;

Similarly, continue in array b.

When a Common Element Is Found

Java
ans += Math.max(sum1, sum2) + a[i];

Suppose:

Code
sum1 = 20
sum2 = 15

Then:

Code
20 + common

This ensures the maximum possible path.

Reset Sums

Java
sum1 = 0;
sum2 = 0;

A new segment starts after the common element.

Move Both Pointers

Java
i++;
j++;

The common element has already been processed.

Remaining Elements

If one array ends earlier:

Java
while(i < a.length)

Collect remaining elements of a.

Similarly:

Java
while(j < b.length)

Collect remaining elements of b.

Final Segment

Java
ans += Math.max(sum1, sum2);

Choose the larger remaining path after the last common element.

Return Answer

Java
return ans;

Complexity Analysis

ComplexityValue
TimeO(n + m)
SpaceO(1)

Each element from both arrays is visited exactly once.

Only a few integer variables are used, so no extra space proportional to input size is required.

Key Takeaways

Summary

This problem can be solved efficiently using a two-pointer approach. By maintaining separate running sums for both arrays and making decisions only at common elements, we always choose the path that yields the maximum cumulative sum. Since each element is processed exactly once, the solution runs in O(n + m) time and uses O(1) extra space, making it both optimal and scalable for large inputs.