Two Pointer Approach
Two Pointer Approach harnesses the properties of sorted arrays to optimize the search process, making it well-suited for scenarios where performance is paramount. By utilizing two pointers to traverse the arrays simultaneously, this approach minimizes computational complexity and memory overhead.
- Initialization: Start with two pointers at the beginning of each array and determine if the total length of both arrays is even or odd.
- Traverse Arrays: Move pointers towards the middle elements of both arrays, comparing elements and updating the middle elements as needed.
- Identify Middle Elements: After traversal, the middle elements are identified.
- Calculate Sum: If the total length is even, return the sum of the two middle elements; if odd, return the single middle element.
Example: To demonstrate finding the sum of the two middle elements of the two sorted arrays using two pointer approach in JavaScript.
function sumMiddle(arr1, arr2) {
let ptr1 = 0;
let ptr2 = 0;
const totalLen = arr1.length + arr2.length;
const isEven = totalLen % 2 === 0;
let mid1, mid2;
for (let i = 0; i <= totalLen / 2; i++) {
mid1 = mid2;
if (arr1[ptr1] === undefined || arr2[ptr2] < arr1[ptr1]) {
mid2 = arr2[ptr2];
ptr2++;
} else {
mid2 = arr1[ptr1];
ptr1++;
}
}
return isEven ? mid1 + mid2 : mid2;
}
const arr1 = [1, 3, 5];
const arr2 = [2, 4, 6];
console.log(sumMiddle(arr1, arr2));
Output
7
Time Complexity: O(min(n, m))
Space Auxiliary: O(1)
Sum of Middle Elements of Two Sorted Arrays using JavaScript
Given 2 sorted arrays Array1 and Array2 of size n each. Merge the given arrays and find the sum of the two middle elements of the merged array.
Example:
Input: array1 = [1, 3, 5] array2 = [2, 4, 6] n = 3
Output: 7
Explanation: Given two sorted arrays ar1 and ar2 of size n each: ar1 = [1, 3, 5] and ar2 = [2, 4, 6]. After merging these arrays, we get [1, 2, 3, 4, 5, 6]. The sum of the two middle elements (3 and 4) is 7. Therefore, the output is 7.
Below are the approaches to find the sum of the middle elements of two arrays using JavaScript:
Table of Content
- Naive Approach
- Using Binary Search
- Two Pointer Approach