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:
Continue in array a
Continue in array b
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;
i traverses array a.
j traverses array b.
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
| Complexity | Value |
|---|
| Time | O(n + m) |
| Space | O(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
Since the arrays are sorted, a two-pointer technique is ideal.
sum1 and sum2 represent the path sums between consecutive common elements.
At each common element, choose the larger accumulated path, add the common element once, and reset the running sums.
This greedy strategy works because decisions only need to be made at common elements, making the solution both optimal and efficient.
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.