Given 2 sorted arrays Ar1 and Ar2 of size N each. Merge the given arrays and find the sum of the two middle elements of the merged array.
Examples:
Input: N = 5
Ar1[] = {1, 2, 4, 6, 10}
Ar2[] = {4, 5, 6, 9, 12}
Output: 11
Explanation: The merged array looks like {1, 2, 4, 4, 5, 6, 6, 9, 10, 12}. Sum of middle elements is 11 (5 + 6).Input: N = 5
Ar1[] = {1, 12, 15, 26, 38}
Ar2[] = {2, 13, 17, 30, 45}
Output: 32
Explanation: The merged array looks like {1, 2, 12, 13, 15, 17, 26, 30, 38, 45} sum of middle elements is 32 (15 + 17).
Naive Approach: To solve the problem by Simply Merging the arrays follow the below steps:
- Create an array merged[] of size 2*n (as both the arrays have the same size n).
- Simultaneously traverse arr1[] and arr2[].
- Pick a smaller of current elements in arr1[] and arr2[], copy this smaller element to the next position in merged[], and move ahead in merged[] and the array whose element is picked.
- If there are remaining elements in arr1[] or arr2[], copy them also in merged[].
- Return the sum of the middle two elements.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <iostream> using namespace std; int findMidSum( int ar1[], int ar2[], int n) { if (n == 1) return ar1[0] + ar2[0]; if (n == 2) return max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]); int i = 0, j = 0; int k = 0; int merged[2 * n]; while (i < n && j < n) { if (ar1[i] <= ar2[j]) { merged[k] = ar1[i]; i++; k++; } else { merged[k] = ar2[j]; j++; k++; } } while (i < n) { merged[k] = ar1[i]; i++; k++; } while (j < n) { merged[k] = ar2[j]; j++; k++; } return merged[n] + merged[n - 1]; } // Drivers code int main() { int ar1[] = { 1, 2, 4, 6, 10 }; int ar2[] = { 4, 5, 6, 9, 12 }; int n = sizeof (ar1) / sizeof (ar1[0]); // Function Call cout << findMidSum(ar1, ar2, n); return 0; } |
Java
// Java code for the above approach: import java.io.*; class GFG { static int findMidSum( int [] ar1, int [] ar2, int n) { if (n == 1 ) { return ar1[ 0 ] + ar2[ 0 ]; } if (n == 2 ) { return Math.max(ar1[ 0 ], ar2[ 0 ]) + Math.min(ar1[ 1 ], ar2[ 1 ]); } int i = 0 , j = 0 ; int k = 0 ; int [] merged = new int [ 2 * n]; while (i < n && j < n) { if (ar1[i] <= ar2[j]) { merged[k] = ar1[i]; i++; k++; } else { merged[k] = ar2[j]; j++; k++; } } while (i < n) { merged[k] = ar1[i]; i++; k++; } while (j < n) { merged[k] = ar2[j]; j++; k++; } return merged[n] + merged[n - 1 ]; } public static void main(String[] args) { int [] ar1 = { 1 , 2 , 4 , 6 , 10 }; int [] ar2 = { 4 , 5 , 6 , 9 , 12 }; int n = ar1.length; // Function call System.out.print(findMidSum(ar1, ar2, n)); } } // This code is contributed by lokesh. |
Python3
def findMidSum(ar1, ar2, n): if n = = 1 : return ar1[ 0 ] + ar2[ 0 ] if n = = 2 : return max (ar1[ 0 ], ar2[ 0 ]) + min (ar1[ 1 ], ar2[ 1 ]) i, j = 0 , 0 k = 0 merged = [ 0 ] * ( 2 * n) while i < n and j < n: if ar1[i] < = ar2[j]: merged[k] = ar1[i] i + = 1 else : merged[k] = ar2[j] j + = 1 k + = 1 while i < n: merged[k] = ar1[i] i + = 1 k + = 1 while j < n: merged[k] = ar2[j] j + = 1 k + = 1 return merged[n] + merged[n - 1 ] # Driver code ar1 = [ 1 , 2 , 4 , 6 , 10 ] ar2 = [ 4 , 5 , 6 , 9 , 12 ] n = len (ar1) # Function call print (findMidSum(ar1, ar2, n)) |
C#
// C# code for the above approach using System; class GFG { // Function to merge the given arrays // and find the sum of the two middle elements // of the merged array. static int findMidSum( int [] ar1, int [] ar2, int n) { if (n == 1) return ar1[0] + ar2[0]; if (n == 2) return Math.Max(ar1[0], ar2[0]) + Math.Min(ar1[1], ar2[1]); int i = 0, j = 0; int k = 0; int [] merged = new int [2 * n]; // merging the arrays while (i < n && j < n) { if (ar1[i] <= ar2[j]) { merged[k] = ar1[i]; i++; k++; } else { merged[k] = ar2[j]; j++; k++; } } while (i < n) { merged[k] = ar1[i]; i++; k++; } while (j < n) { merged[k] = ar2[j]; j++; k++; } return merged[n] + merged[n - 1]; } // Drivers code static void Main() { int [] ar1 = { 1, 2, 4, 6, 10 }; int [] ar2 = { 4, 5, 6, 9, 12 }; int n = ar1.Length; // Function Call Console.WriteLine(findMidSum(ar1, ar2, n)); } } |
Javascript
function findMidSum(ar1, ar2, n) { if (n === 1) return ar1[0] + ar2[0]; if (n === 2) return Math.max(ar1[0], ar2[0]) + Math.min(ar1[1], ar2[1]); let i = 0, j = 0, k = 0; let merged = new Array(2 * n); while (i < n && j < n) { if (ar1[i] <= ar2[j]) { merged[k] = ar1[i]; i++; k++; } else { merged[k] = ar2[j]; j++; k++; } } while (i < n) { merged[k] = ar1[i]; i++; k++; } while (j < n) { merged[k] = ar2[j]; j++; k++; } return merged[n] + merged[n - 1]; } // Drivers code let ar1 = [1, 2, 4, 6, 10]; let ar2 = [4, 5, 6, 9, 12]; let n = ar1.length; // Function Call console.log(findMidSum(ar1, ar2, n)); |
11
Time Complexity: O(n), Since we are traversing both arrays, the time complexity is O(2*n)
Auxiliary Space: O(n), As we are using one extra array to store the merged array elements
Optimized Approach: To optimize our previous approach we will use a counter to decrease the auxiliary space used.
Follow the steps to solve the problem:
- Simultaneously traverse arr1[] and arr2[].
- Use count to keep track of the nth element and (n+1)th element ( for an array of 2*n size, nth and (n+1)th elements are the middle elements).
- Pick the smaller of the current elements in arr1[] and arr2[], update the m1 with m2 and m2 with the smaller element, and move the pointer of the array whose element is picked.
- At the end of the loop, m1 will have the nth element, and m2 will have the n+1th element. Return m1+m2.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; int findMidSum( int ar1[], int ar2[], int n) { if (n == 1) return ar1[0] + ar2[0]; if (n == 2) return max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]); // Current index of i/p array ar1[] int i = 0; // Current index of i/p array ar2[] int j = 0; int count; int m1 = -1, m2 = -1; // Since there are 2n elements, median // will be average of elements at // index n-1 and n in the array // obtained after merging ar1 and ar2 for (count = 0; count <= n; count++) { // Below is to handle case where // all elements of ar1[] are // smaller than smallest(or first) // element of ar2[] if (i == n) { m1 = m2; m2 = ar2[0]; break ; } // Below is to handle case where // all elements of ar2[] are // smaller than smallest(or first) // element of ar1[] else if (j == n) { m1 = m2; m2 = ar1[0]; break ; } // equals sign because if two // arrays have some common elements if (ar1[i] <= ar2[j]) { // Store the prev median m1 = m2; m2 = ar1[i]; i++; } else { // Store the prev median m1 = m2; m2 = ar2[j]; j++; } } return (m1 + m2); } // Drivers code int main() { int ar1[] = { 1, 2, 4, 6, 10 }; int ar2[] = { 4, 5, 6, 9, 12 }; int n = sizeof (ar1) / sizeof (ar1[0]); // Function Call cout << findMidSum(ar1, ar2, n); return 0; } |
Java
import java.util.*; public class MedianOfSortedArrays { public static int findMidSum( int [] ar1, int [] ar2, int n) { if (n == 1 ) return ar1[ 0 ] + ar2[ 0 ]; if (n == 2 ) return Math.max(ar1[ 0 ], ar2[ 0 ]) + Math.min(ar1[ 1 ], ar2[ 1 ]); // Current index of i/p array ar1[] int i = 0 ; // Current index of i/p array ar2[] int j = 0 ; int count; int m1 = - 1 , m2 = - 1 ; // Since there are 2n elements, median // will be average of elements at // index n-1 and n in the array // obtained after merging ar1 and ar2 for (count = 0 ; count <= n; count++) { // Below is to handle case where // all elements of ar1[] are // smaller than smallest(or first) // element of ar2[] if (i == n) { m1 = m2; m2 = ar2[ 0 ]; break ; } // Below is to handle case where // all elements of ar2[] are // smaller than smallest(or first) // element of ar1[] else if (j == n) { m1 = m2; m2 = ar1[ 0 ]; break ; } // equals sign because if two // arrays have some common elements if (ar1[i] <= ar2[j]) { // Store the prev median m1 = m2; m2 = ar1[i]; i++; } else { // Store the prev median m1 = m2; m2 = ar2[j]; j++; } } return (m1 + m2); } // Drivers code public static void main(String[] args) { int [] ar1 = { 1 , 2 , 4 , 6 , 10 }; int [] ar2 = { 4 , 5 , 6 , 9 , 12 }; int n = ar1.length; // Function Call System.out.println(findMidSum(ar1, ar2, n)); } } |
Python3
def find_mid_sum(ar1, ar2, n): if n = = 1 : # If there's only 1 element in each array return ar1[ 0 ] + ar2[ 0 ] # Return the sum of the single elements if n = = 2 : # If there are 2 elements in each array return max (ar1[ 0 ], ar2[ 0 ]) + min (ar1[ 1 ], ar2[ 1 ]) # Return the sum of the smaller from first and larger from second array, and vice versa i = 0 j = 0 m1 = - 1 m2 = - 1 for count in range (n + 1 ): # Iterate through both arrays if i = = n: # If all elements in first array are used m1 = m2 m2 = ar2[j] break elif j = = n: # If all elements in second array are used m1 = m2 m2 = ar1[i] break if ar1[i] < = ar2[j]: # Compare current elements from both arrays m1 = m2 # Move the "merged" element forward m2 = ar1[i] # Set the smaller element from the first array i + = 1 else : m1 = m2 # Move the "merged" element forward m2 = ar2[j] # Set the smaller element from the second array j + = 1 return m1 + m2 # Return the sum of the two middle elements # Driver code ar1 = [ 1 , 2 , 4 , 6 , 10 ] ar2 = [ 4 , 5 , 6 , 9 , 12 ] n = len (ar1) # Function call print (find_mid_sum(ar1, ar2, n)) |
C#
// C# code for the above approach: using System; public class MedianOfSortedArrays { public static int findMidSum( int [] ar1, int [] ar2, int n) { if (n == 1) return ar1[0] + ar2[0]; if (n == 2) return Math.Max(ar1[0], ar2[0]) + Math.Min(ar1[1], ar2[1]); // Current index of i/p array ar1[] int i = 0; // Current index of i/p array ar2[] int j = 0; int count; int m1 = -1, m2 = -1; // Since there are 2n elements, median // will be average of elements at // index n-1 and n in the array // obtained after merging ar1 and ar2 for (count = 0; count <= n; count++) { // Below is to handle case where // all elements of ar1[] are // smaller than smallest(or first) // element of ar2[] if (i == n) { m1 = m2; m2 = ar2[0]; break ; } // Below is to handle case where // all elements of ar2[] are // smaller than smallest(or first) // element of ar1[] else if (j == n) { m1 = m2; m2 = ar1[0]; break ; } // equals sign because if two // arrays have some common elements if (ar1[i] <= ar2[j]) { // Store the prev median m1 = m2; m2 = ar1[i]; i++; } else { // Store the prev median m1 = m2; m2 = ar2[j]; j++; } } return (m1 + m2); } // Drivers code public static void Main() { int [] ar1 = { 1, 2, 4, 6, 10 }; int [] ar2 = { 4, 5, 6, 9, 12 }; int n = ar1.Length; // Function Call Console.WriteLine(findMidSum(ar1, ar2, n)); } } // This code is contributed by Utkarsh Kumar |
Javascript
function findMidSum(ar1, ar2, n) { if (n == 1) return ar1[0] + ar2[0]; if (n == 2) return Math.max(ar1[0], ar2[0]) + Math.min(ar1[1], ar2[1]); // Current index of i/p array ar1[] let i = 0; // Current index of i/p array ar2[] let j = 0; let count; let m1 = -1, m2 = -1; // Since there are 2n elements, median // will be average of elements at // index n-1 and n in the array // obtained after merging ar1 and ar2 for (count = 0; count <= n; count++) { // Below is to handle case where // all elements of ar1[] are // smaller than smallest(or first) // element of ar2[] if (i == n) { m1 = m2; m2 = ar2[0]; break ; } // Below is to handle case where // all elements of ar2[] are // smaller than smallest(or first) // element of ar1[] else if (j == n) { m1 = m2; m2 = ar1[0]; break ; } // equals sign because if two // arrays have some common elements if (ar1[i] <= ar2[j]) { // Store the prev median m1 = m2; m2 = ar1[i]; i++; } else { // Store the prev median m1 = m2; m2 = ar2[j]; j++; } } return (m1 + m2); } // Driver's code to test above function let ar1 = [ 1, 2, 4, 6, 10 ]; let ar2 = [ 4, 5, 6, 9, 12 ]; let n = ar1.length; // Function Call console.log(findMidSum(ar1, ar2, n)); // This code is contributed by Chandan Agarwal |
11
Time Complexity: O(n)
Auxiliary Space: O(1), Since we have used count, m1 and m2 to keep track of the middle elements
Efficient Approach: To solve the problem in the most efficient way we will use Binary search:
- Initialize low = 0 and high = n, where n is the size of the first array.
- Find the point to partition the ar1 into 2 parts using Binary Search.
- First halve should have the elements smaller or equal to the first middle element and second halve should have the element greater or equal to the second middle element. And each half will have n elements.
- Using the partition point of ar1, find the partition point for ar2.
- Check whether all the elements in first half is smaller than second half.
- l1 = largest element of the first half from ar1
- l2 = largest element of the first half from ar2
- r1 = smallest element of the second half from ar1
- r2 = smallest element of the second half from ar2
- Since l1 is already less than r1 and l2 is already less than r2,
- if(l1 > r2)
- high = cut1 – 1
- if(l2 > r1)
- low = cut1+1
- else
- return max(l1, l2) + min(r1, r2)
- if(l1 > r2)
- Since max of the largest elements of first halves from ar1 and ar2 will be the maximum in first half and min of the smallest elements from second halves from ar1 and ar2 will be the smallest in the second half, return the sum of the max(l1, l2) and min(r1, r2).
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; int findMidSum( int ar1[], int ar2[], int n) { if (n == 1) { return ar1[0] + ar2[0]; } if (n == 2) { return max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]); } // code here int low = 0, high = n - 1; int ans = -1; while (low <= high) { int cut1 = low + (high - low) / 2; int cut2 = n - cut1; int l1 = (cut1 == 0 ? INT_MIN : ar1[cut1 - 1]); int l2 = (cut2 == 0 ? INT_MIN : ar2[cut2 - 1]); int r1 = (cut1 == n ? INT_MAX : ar1[cut1]); int r2 = (cut2 == n ? INT_MAX : ar2[cut2]); if (l1 > r2) { high = cut1 - 1; } else if (l2 > r1) { low = cut1 + 1; } else { ans = max(l1, l2) + min(r1, r2); break ; } } return ans; } // C++ code for the above approach: int main() { int ar1[] = { 1, 2, 4, 6, 10 }; int ar2[] = { 4, 5, 6, 9, 12 }; int n = sizeof (ar1) / sizeof (ar1[0]); // Function Call cout << findMidSum(ar1, ar2, n); return 0; } |
Java
import java.util.*; public class Main { // Function to find the maximum sum of elements after dividing two sorted arrays at any point public static int findMidSum( int [] ar1, int [] ar2, int n) { if (n == 1 ) { // If there is only one element in each array, return their sum return ar1[ 0 ] + ar2[ 0 ]; } if (n == 2 ) { // If there are two elements in each array, return the sum of the maximum from one and the minimum from the other return Math.max(ar1[ 0 ], ar2[ 0 ]) + Math.min(ar1[ 1 ], ar2[ 1 ]); } int low = 0 , high = n - 1 ; int ans = - 1 ; while (low <= high) { int cut1 = low + (high - low) / 2 ; // Find the midpoint in the first array int cut2 = n - cut1; // Calculate the corresponding midpoint in the second array int l1 = (cut1 == 0 ) ? Integer.MIN_VALUE : ar1[cut1 - 1 ]; int l2 = (cut2 == 0 ) ? Integer.MIN_VALUE : ar2[cut2 - 1 ]; int r1 = (cut1 == n) ? Integer.MAX_VALUE : ar1[cut1]; int r2 = (cut2 == n) ? Integer.MAX_VALUE : ar2[cut2]; if (l1 > r2) { // If the left element of the first array is greater than the right element of the second array, // move the partition point to the left in the first array high = cut1 - 1 ; } else if (l2 > r1) { // If the left element of the second array is greater than the right element of the first array, // move the partition point to the right in the first array low = cut1 + 1 ; } else { // If neither of the above conditions is met, it means we've found the correct partition points. // Calculate the maximum of the left elements and the minimum of the right elements and return the sum. ans = Math.max(l1, l2) + Math.min(r1, r2); break ; } } return ans; } public static void main(String[] args) { int [] ar1 = { 1 , 2 , 4 , 6 , 10 }; int [] ar2 = { 4 , 5 , 6 , 9 , 12 }; int n = ar1.length; System.out.println(findMidSum(ar1, ar2, n)); } } |
Python3
def find_mid_sum(ar1, ar2, n): if n = = 1 : return ar1[ 0 ] + ar2[ 0 ] if n = = 2 : return max (ar1[ 0 ], ar2[ 0 ]) + min (ar1[ 1 ], ar2[ 1 ]) low = 0 high = n - 1 ans = - 1 while low < = high: cut1 = low + (high - low) / / 2 cut2 = n - cut1 l1 = ar1[cut1 - 1 ] if cut1 ! = 0 else float ( '-inf' ) l2 = ar2[cut2 - 1 ] if cut2 ! = 0 else float ( '-inf' ) r1 = ar1[cut1] if cut1 ! = n else float ( 'inf' ) r2 = ar2[cut2] if cut2 ! = n else float ( 'inf' ) if l1 > r2: high = cut1 - 1 elif l2 > r1: low = cut1 + 1 else : ans = max (l1, l2) + min (r1, r2) break return ans # Main function if __name__ = = "__main__" : ar1 = [ 1 , 2 , 4 , 6 , 10 ] ar2 = [ 4 , 5 , 6 , 9 , 12 ] n = len (ar1) # Function Call print (find_mid_sum(ar1, ar2, n)) |
C#
using System; class Program { // Function to find the maximum sum of elements from two sorted arrays // such that the elements are picked alternately from each array static int FindMidSum( int [] ar1, int [] ar2, int n) { if (n == 1) { return ar1[0] + ar2[0]; } if (n == 2) { // If there are only two elements, pick the maximum from each array return Math.Max(ar1[0], ar2[0]) + Math.Min(ar1[1], ar2[1]); } int low = 0, high = n - 1; int ans = -1; // Binary search for the optimal cut positions while (low <= high) { int cut1 = low + (high - low) / 2; int cut2 = n - cut1; // Calculate left and right elements for both arrays int l1 = (cut1 == 0) ? int .MinValue : ar1[cut1 - 1]; int l2 = (cut2 == 0) ? int .MinValue : ar2[cut2 - 1]; int r1 = (cut1 == n) ? int .MaxValue : ar1[cut1]; int r2 = (cut2 == n) ? int .MaxValue : ar2[cut2]; if (l1 > r2) { // Adjust the search range to the left high = cut1 - 1; } else if (l2 > r1) { // Adjust the search range to the right low = cut1 + 1; } else { // Calculate the maximum sum with elements picked alternately ans = Math.Max(l1, l2) + Math.Min(r1, r2); break ; } } return ans; } // Driver code static void Main() { int [] ar1 = { 1, 2, 4, 6, 10 }; int [] ar2 = { 4, 5, 6, 9, 12 }; int n = ar1.Length; // Function Call Console.WriteLine(FindMidSum(ar1, ar2, n)); } } |
11
Time Complexity: O(logn)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!