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() <= 103
1 <= arr1[i] <= 106
1 <= arr2[i] <= 106
Approach 01:
-
C++
-
Python
#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.