Introduction
This blog will discuss the various approaches to solve the Sum of middle elements of two sorted arrays problem. Before jumping into the problem of getting the Sum of middle elements of two sorted arrays, let’s first understand a sorted array.
A sorted array is one of the combinations of the array in which all the elements of the array are either in non-increasing order or non-decreasing order.
Example:
Input: arr = [5, 4, 3, 10, 15, 25, 2, 100]
Sorted Array:- [2, 3, 4, 5, 10, 15, 25, 100]
In this Sum of middle elements of two sorted arrays problem, we need to return the sum of the array's middle elements after merging the two given sorted arrays. In this Sum of middle elements of two sorted arrays problem, our result will be the sum of two middle elements if the size of the resultant merged array is even, which means there will be two middle elements.
Note: The size of two sorted arrays is the same, i.e., ‘N’, which means the size of the resultant array will be ‘2N’.
Must Read, Array Implementation of Queue and Rabin Karp Algorithm
Brute Force Approach
Brute Force Solution considers merging both the sorted arrays using merge sort. While comparing the elements of both the sorted arrays, we need to keep the track of the count, and when the count is equal to ‘N’ that will simply mean that we are in the center of the resultant array, and we need to take the sum of the elements at the index equal to count and one index which is before that count index.
Algorithm
Step 1. Create a function ‘getResult()’ that will accept 3 parameters, i.e., 2 sorted arrays naming ‘arr1’, ‘arr2’, and size of the sorted array ‘N’.
Step 2. Initialize two variables ‘x’, ‘y’ with zero, each one for each sorted array.
Step 3. Declare three variables, ‘Count’:- to keep track of the index, ‘median1’ and ‘median2’:- to store the value of two middle elements.
Step 4. Make an iteration using the ‘count’ variable from 0 until its value is less than or equal to ‘N’.
Step 5. Provide two edge cases, taking into account the value of ‘i’ and ‘j’, if they are equal to ‘N’, which means that they are the end of their respective sorted array, in this case, assign the value of ‘median2’ to ‘median1’ and initialize ‘median1’ with the first index of ‘arr2’.
Step 6. Similarly, if ‘j’ is equal to ‘N’, then assign the value of ‘median2’ to ‘median1’ and initialize ‘median1’ with the first index of ‘arr1’.
Step 7. Compare both the elements of the sorted array with ‘i’ and ‘j’ index and if ‘arr1[i]’ is less than or equal to ‘arr2[j]’ then store the previous median and increment the ‘i’ and if it is greater than ‘arr2[j]’ then increment the ‘j’.
Step 8. Now, return the sum of ‘median1’ and ‘median2’.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
int getResult(int arr1[], int arr2[], int n)
{
int i = 0;
int j = 0;
int count;
int median1 = -1, median2 = -1;
for (count = 0; count <= n; count++)
{
// Edge cases
if (i == n)
{
median1 = median2;
median2 = arr2[0];
break;
}
else if (j == n)
{
median1 = median2;
median2 = arr1[0];
break;
}
if (arr1[i] <= arr2[j])
{
/* Store the previous median */
median1 = median2;
median2 = arr1[i];
i++;
}
else
{
/* Store the previous median */
median1 = median2;
median2 = arr2[j];
j++;
}
}
return (median1 + median2);
}
int main()
{
int arr1[] = {5, 10, 78, 98, 100, 114};
int arr2[] = {45, 70, 88, 94, 150, 164};
int N = sizeof(arr1) / sizeof(arr1[0]);
int res = getResult(arr1, arr2, N);
cout << "Sum of middle element of two sorted arrays is :- " << res;
}
Output :
Sum of middle element of two sorted arrays is :- 182Complexity Analysis
Time Complexity: O(N)
Incall to ‘getResult()’, we are traversing for ‘N’ times in the worst case, therefore, the overall time complexity is O(N).
Space Complexity: O(1)
As we are using constant space, therefore, the overall space complexity will be O(1).
Check out this array problem - Merge 2 Sorted Arrays
569+ registered 
