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

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

Output

35

Explanation

Possible path:

1 → 5 → 7 → 10 → 12

Sum:

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:

a[i] < b[j]

Add the element to sum1.

Case 2

If:

a[i] > b[j]

Add the element to sum2.

Case 3

If:

a[i] == b[j]

A common element is found.

Now we have two paths:

Previous Common
       |
   sum1 path

Previous Common
       |
   sum2 path

Take the better one.

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

Now add the common element only once.

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:

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

Dry Run

Input

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

Initially

sum1 = 0
sum2 = 0
ans = 0

Step 1

2 > 1

sum2 = 1

Step 2

2 < 5

sum1 = 2

Step 3

3 < 5

sum1 = 5

Step 4

Common element:

7 == 7

Current sums:

sum1 = 5
sum2 = 6

Choose maximum:

ans = 6 + 7 = 13

Reset:

sum1 = 0
sum2 = 0

Continue

Remaining:

a : 10 12
b : 8

sum1 = 22
sum2 = 8

Take larger:

ans += 22

Final Answer

13 + 22 = 35

Code

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

int i = 0;
int j = 0;

Running Sums

int sum1 = 0;
int sum2 = 0;

These store the sum collected since the last common element.

Final Answer

int ans = 0;

Stores the maximum path sum.

Traverse Both Arrays

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

Continue until one array finishes.

When Element in a Is Smaller

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

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

Similarly, continue in array b.

When a Common Element Is Found

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

Suppose:

sum1 = 20
sum2 = 15

Then:

20 + common

This ensures the maximum possible path.

Reset Sums

sum1 = 0;
sum2 = 0;

A new segment starts after the common element.

Move Both Pointers

i++;
j++;

The common element has already been processed.

Remaining Elements

If one array ends earlier:

while(i < a.length)

Collect remaining elements of a.

Similarly:

while(j < b.length)

Collect remaining elements of b.

Final Segment

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

Choose the larger remaining path after the last common element.

Return Answer

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.