Median of two sorted arrays

Given 2 sorted integer arrays arr1 and arr2. Find the median of two sorted arrays arr1 and arr2.

Examples:

Input: arr1 = [1, 2, 4, 6, 10], arr2 = [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: arr1 = [1, 12, 15, 26, 38], arr2 = [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).

Expected Time Complexity: O(log n)
Expected Auxiliary Space: O(1)

Constraints:
1 <= arr1.size() == arr2.size() <= 10³
1 <= arr1[i] <= 10⁶
1 <= arr2[i] <= 10⁶

Approach 01:

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    // Function to calculate the sum of middle elements of merged and sorted arrays.
    int SumofMiddleElements(vector<int>& arr1, vector<int>& arr2) {
        // Extend arr1 with elements of arr2.
        arr1.insert(arr1.end(), arr2.begin(), arr2.end());
        
        // Sort the merged array.
        sort(arr1.begin(), arr1.end());
        
        int n = arr1.size();
        
        // Check if the size of the array is even or odd.
        if (n % 2 == 0) {
            // If even, return the sum of the two middle elements.
            return arr1[(n / 2) - 1] + arr1[n / 2];
        } else {
            // If odd, return the middle element.
            return arr1[n / 2];
        }
    }
};

class Solution:
    def sum_of_middle_elements(self, arr1, arr2):
        arr1.extend(arr2)
        arr1.sort()
        n = len(arr1)
        
        if( n%2==0):
            return arr1[(n//2)-1]+arr1[(n//2)]
        else:
            return arr1[(n//2)]

Time Complexity

• Merging Arrays:

  The merging operation, which involves appending `arr2` to `arr1`, takes \( O(n_1 + n_2) \) time, where \( n_1 \) and \( n_2 \) are the sizes of `arr1` and `arr2`, respectively.

• Sorting the Merged Array:

  The sorting operation on the merged array takes \( O((n_1 + n_2) \log(n_1 + n_2)) \) time, where \( n_1 + n_2 \) is the total number of elements in the merged array.

• Overall Time Complexity:

  The overall time complexity is dominated by the sorting operation, which is \( O((n_1 + n_2) \log(n_1 + n_2)) \).

Space Complexity

• Space for Merged Array:

  Space is required for the merged array, which is \( O(n_1 + n_2) \) in size. This is the additional space used by the function.

• Auxiliary Space for Sorting:

  The sorting algorithm may use additional space for internal operations, but it is generally \( O(\log(n_1 + n_2)) \) for the typical in-place sorting algorithms.

• Overall Space Complexity:

  The overall space complexity is \( O(n_1 + n_2) \), dominated by the space needed for the merged array.