Last Updated: 25 Dec, 2020
Median of two sorted arrays
Hard
Asked in companies
Given two sorted arrays 'a' and 'b' of size 'n' and 'm' respectively.
Find the median of the two sorted arrays.
Median is defined as the middle value of a sorted list of numbers. In case the length of list is even, median is the average of the two middle elements.
The expected time complexity is O(min(logn, logm)), where 'n' and 'm' are the sizes of arrays 'a' and 'b', respectively, and the expected space complexity is O(1).
Example:
Input: 'a' = [2, 4, 6] and 'b' = [1, 3, 5]
Output: 3.5
Explanation: The array after merging 'a' and 'b' will be { 1, 2, 3, 4, 5, 6 }. Here two medians are 3 and 4. So the median will be the average of 3 and 4, which is 3.5.
Input format:
The first line contains two space-separated integers ‘n’ and ‘m’ representing the sizes of the two arrays.
The second line contains 'n' space-separated integers representing the elements of the first array.
The third line contains 'm' space-separated integers representing the elements of the second array.
Output format :
Print a single line containing a single value denoting the median of the combined array.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function and return the median of the two arrays.
Approaches
The first approach is by joining the array and again sorting is to get median.
The algorithm is as follows:
- Create a new array of size of total number of elements.
- Insert elements of both the arrays in the array.
- Sort the array and find the median.
The second approach is using a two-pointer approach to get middle elements.
The algorithm is as follows:
- Initialize two pointers i and j to 0.
- Move a pointer forward which has a smaller value.
- Move the pointers until we process half the number of elements.
- Then calculate the median.
The third approach is using binary search to find median.
The algorithm is as follows:
- Use Binary Search to partition the smaller array in two parts.
- Find the partition of the second array such that the sum of elements on the left side of the partition in both the arrays has half of the total elements.
- Check if this partition is valid by verifying if the largest number of left partitions is smaller than the smallest number of the right partitions.
- If the partition is valid then calculate and return the median.
Similar problems