Input: nums1 = [1,3], nums2 = [2,4]
Output: 2.5
Explanation: after merging input arrays = [1, 2,3 ,4] and median will be (2 + 3) / 2 = 2.5..
Input: nums1 = [1,4,9], nums2 = [3,7,8]
Output: 5.5
Explanation: after merging input arrays = [1,3, 4,7 ,8,9] and median is (4 + 7) / 2 = 5.5.
Since the given input arrays are same in size n, resultant array after merge will be of size
2n, that's an even length array. So, the median will be the average of two middle indexed elements
(result[midIndex] + result[midIndex-1]) / 2 .
Solutions
- Using MergeSort approach - merge input arrays first, then take median
- Using MergeSort approach - compute median while merging, without extra space
- Efficient approach - Using Binary search and comparing median of input arrays
In this approach, we are going to merge input arrays first, using merge approach used in MergeSort.
Now we know that that the resultant array length is an even lenth array, so take median as (result[midIndex-1] + result[midIndex]) / 2 .
Steps:
-
Let's declare two variables i=0 and j=0 to track the indexes of nums1 and nums2 respectively.
-
Compare numbers from both arrays and take the smallest number into result array and repeat
this process until one of the array is fully done.
-
Copy any remaining numbers from nums1 or nums2.
-
Now, you have result array fully sorted and you can take median of the resultant array.
Complexity:
Merging two sorted arrays, takes O (n) run time and takes O (n) space as we are
copying sorted numbers into a resultant array.
/**
* Utility method to compute median of a given array
* @param array input array
* @return median of input array, and throws IllegalArgumentException if the input array is Null or empty
*/
private static double getMedian(int[] array) {
if(array == null || array.length ==0) {
throw new IllegalArgumentException("input array cannot be null or empty");
}
if(array.length % 2 == 0) { // resultant array is an even length array
int midIndex = array.length/2;
return (double)(array[midIndex] + array[midIndex-1]) /2;
}
// if the resultant array is an odd length array
return array[array.length/2];
}
/**
*
* Merges input arrays first and then take the median
*
* @param nums1 sorted array1
* @param nums2 sorted array2
* @return median of resultant array after merging
*/
public static double medianUsingMergeSortApproach1(int[] nums1, int[] nums2) {
//base cases
if(nums1 == null || nums1.length == 0) { // if nums1 array is null or empty, result array will be nums2
return getMedian(nums2);
} else if (nums2 == null || nums2.length ==0) { // if nums2 array is null or empty, result array will be nums1
return getMedian(nums1);
}
int[] result = new int[nums1.length + nums2.length];
int i = 0; // index to track nums1 array
int j = 0; // index to track nums2 array
for(int k=0; k<result.length; k++) {
if(i<nums1.length && j<nums2.length) {
if(nums1[i]<=nums2[j]) { // if nums1 has smaller number take that into result array
result[k] = nums1[i];
i++;
} else {
result[k] = nums2[j]; // if nums2 has smaller number take that into result array
j++;
}
} else {
// copy any remaining elements from nums1 (or) nums2
if(i<nums1.length) {
result[k] = nums1[i];
i++;
}
if(j<nums2.length) {
result[k] = nums2[j];
j++;
}
}
}
return getMedian(result);
}
The main idea in this approach is, whether the input array length n is odd or even,
we need to find out the middle two numbers from the resultant array.
In the merge() process of MergeSort algorithm,
we compare elements from left array to right array and start copy them in sorting order into resultant array,
but we only need middle two numbers, so we can just do n+1 comparisons and take the values comes at
n-1th comparison and nth comparison (Because, in Java array indexes starts with 0).
Let's take an example, say the given input arrays are nums1 = [1,4,9] and nums2 = [3,7,8] ,
when you merge them, this is the resultant array [1,3, 4,7 ,8,9],
so the numbers required to compute median are located at 2nd and 3rd
indexes. Since the array size in n, we need n+1 comparisons.
Steps:
-
Let's declare two variables i=0 and j=0 to track the indexes of nums1 and nums2 respectively.
-
Declare two more variables m1=-1 and m2=-1 to store large numbers seen so far as we compare input arrays.
-
In a for loop from 0 to n (inclusive) compare the elements from nums1 and nums2
and store the higher number into m2 (before storing it, copy the previous value from m2 into m1).
- If the highest number is taken from nums1 array, then increment i.
- If the highest number is taken from nums2 array, then increment j.
-
There could be two other scenarios, where i will reach n, that means all numbers in nums1
array are smaller than the numbers from nums2 array, in this case take first element from nums2 as m2.
-
Other scenario, where j will reach n, that means all numbers in nums2
array are smaller than the numbers from nums1 array, in this case take first element from nums1 as m2.
-
Once we have m1 and m2 values, take median as (m1 + m2) /2 .
Complexity:
For loop runs n times, so it takes O (n) run time where n is the size of input array,
and takes O (1) space as we are storing middle two numbers only into two temporary variables.
public static double median(int[] nums1, int[] nums2, int n) {
int i=0; // index to keep track of nums1
int j=0; //index to keep track of nums2
int m1=-1; // temporary variable to hold 1st mid element
int m2=-2;// temporary variable to hold 2n mid element
for (int k =0; k<= n; k++) { // looping to n+1 times to compare elements as our median would be
// from n-1 index element from first array and 0th index from second array
// when the array is fully merged and sorted [0,1,2....n-1] [0,1,2....n-1]
if(i == n) { // where nums1 array elements are smaller than nums2,
// so i is incremented to the end index of nums1 array
// median would be nums1[n-1] = last element from nums1
// and nums2[0] = first element from nums2
m1 = m2;
m2 = nums2[0];
break;
}
if(j == n) { // where nums2 array elements are smaller than nums1
m1 = m2;
m2 = nums1[0];
break;
}
// keep copying the smallest out of nums1 and nums2 into m1 and m2
if(nums1[i]<=nums2[j]){
m1 = m2;
m2 = nums1[i];
i++;
} else {
m1 = m2;
m2 = nums2[j];
j++;
}
}
return (double) (m1+m2)/2;
}
In this approach, we are going to find out indexes from both input arrays where the median will reside using a binary search,
the key here is, how we choose those indexes.
The main idea here is, since the input arrays are already sorted, and when input arrays are merged, it wil have elements from both arrays
at the median, and our task is to find such indexes.
Solution
-
If the input arrays length is 1, say A = [a1] and B = [b1], then median is simply a1 + b1 /2.
-
If the input arrays length is 2, say A = [a1, a2] and B = [b1, b2], ad when the arrays are merged resultant array will be [Min(a1, b1), Max(a1, b1)
, Min(a2, b2), Max(a2, b2)]. So the median is simply Max(a1, b1) + Min(a2, b2) /2.
-
If the input array length is greater than 2, then we can compare medians of two input arrays m1 and m2, and check one of the following.
-
If m1 == m2, then we have found our answer, return median.
Example: A = [1, 3 ,5] and B = [2, 3, 7], so median of array A will be m1 = 3 and median of array B will be m2 = 3. Since m1 and m2 are same we can return either m1 or m2.
-
If m1 < m2, then the median should be in this range from arrays A and B,
A = [......m1........endA] and B = [startB......m2.......].
Example: A = [1, 2, 3, 6] and B = [4, 6, 8, 10], so median of array A will be m1 = 2.5 and median of array B will be m2 = 7.
Since m1 < m2, median should be in these sub arrays A = [3, 6] and B = [4, 6].
-
If m1 > m2, then the median should be in this range from arrays A and B,
A = [startA......m1........] and B = [......m2.......endB].
Example: A = [4, 6, 8, 10] and B = [1, 2, 3, 6], so median of array A will be m1 = 7 and median of array B will be m2 = 2.5.
Since m1 > m2, median should be in these sub arrays A = [4, 6] and B = [3, 6].
-
Repeat above steps on the smaller sub arrays, if you notice above two cases where m1 < m2 or m1 > m2,
we are reducing the input array size by half.
Complexity:
Time complexity will be log (n) times, because in each iteration, depeding on the medians of input arrays, we are reducing search range by half.
Space complexity will be O (1).
public static double median_Using_Binary_Search(int[] nums1, int[] nums2) {
if(nums1.length == 0) { // base case if input arrays have only one element
return (double) (nums1[0] + nums2[0])/2;
}
return median_Using_Binary_Search_Recursive(nums1,nums2, 0, nums1.length-1, 0, nums2.length-1);
}
public static double getMedian(int[] input, int start, int end) {
int length = end -start +1; // since index starts from 0
int mid = length /2;
if((length % 2) == 0) { // even array
return (double)(input[mid-1] + input[mid]) / 2;
} else {
return input[mid];
}
}
/**
*
* @param nums1
* @param nums2
* @param startA - start index of nums1 array
* @param endA - end index of nums1 array
* @param startB - start index of nums2 array
* @param endB - end index of nums2 array
* @return
*/
public static double median_Using_Binary_Search_Recursive(int[] nums1, int[] nums2, int startA, int endA, int startB, int endB) {
if (endA - startA == 1 && endB - startB == 1) { // If the nums1 array has only two elements
// nums2 size is also same as nums1, per problem statement
return (double)(Math.max(nums1[startA], nums2[startB]) + Math.min(nums1[endA], nums2[endB]) ) /2;
}
double m1 = getMedian(nums1, startA, endA);
double m2 = getMedian(nums2, startB, endB);
// if both medians are same, return either of them
if(m1 == m2) {
return m1;
}
int length = (endA - startA +1);
boolean isEven = length % 2==0;
int mid = isEven ? length/2-1 : length/2;
// if m1 < m2 then the median will be between m1,endA from nums1[.... m1 ....endA...]
// and startB and m2 of nums2 [...startB....m2...]
if(m1<m2) {
return median_Using_Binary_Search_Recursive(nums1, nums2, startA+(mid), endA, startB, endB - (mid));
} else {
return median_Using_Binary_Search_Recursive(nums1, nums2, startA, endA-mid, startB+mid, endB);
}
}
Similar Articles
-
Median of two sorted arrays of different size
Above examples source code can be found at
GitHub link for Java code