Median of two sorted Arrays of different sizes in Java
The median of two sorted arrays of different sizes is the middle element that divides the combined set into two equal halves. It is a commonly encountered problem in computer science, particularly in the field of data structures and algorithms. In this article, we will discuss how to find the median of two sorted arrays of different sizes in Java.
Algorithm:
Step 1: Find the lengths of the two input arrays and initialize an empty array to hold the merged array.
Step 2: Merge the two input arrays into a single sorted array using the merge function of merge sort, keeping track of the index positions of each input array.
Step 3: If the combined length of the two input arrays is odd, return the middle element of the merged array.
Step 4: If the combined length of the two input arrays is even, return the average of the two middle elements of the merged array.
Pseudocode for above algoritm:
function findMedianSortedArrays(nums1, nums2)
m = length of nums1
n = length of nums2
merged = empty array of size m + n
i = j = k = 0
// Merge the two sorted arrays into a single sorted array
while i < m and j < n
if nums1[i] <= nums2[j]
merged[k] = nums1[i]
i++
else
merged[k] = nums2[j]
j++
k++
end while
// Copy the remaining elements of nums1 into the merged array
while i < m
merged[k] = nums1[i]
i++
k++
end while
// Copy the remaining elements of nums2 into the merged array
while j < n
merged[k] = nums2[j]
j++
k++
end while
// Find the median of the combined set
if (m + n) % 2 == 0
mid = (m + n) / 2
return (merged[mid - 1] + merged[mid]) / 2.0
else
mid = (m + n) / 2
return merged[mid]
end if
end function
Explanation:
we first merge the two arrays into a single sorted array using the merge function of merge sort. We then find the median of the merged array using the straightforward approach described earlier. If the combined set has an odd number of elements, we return the middle element. If the combined set has an even number of elements, we return the average of the two middle elements.
Program:
File name: MedianOfTwoSortedArrays.java
import java.util.Arrays;
public class MedianOfTwoSortedArrays {
public static void main(String[] args) {
int[] nums1 = {1, 3, 5, 7, 9}; // first sorted array
int[] nums2 = {2, 4, 6, 8}; // second sorted array
double median = findMedianSortedArrays(nums1, nums2);
System.out.println("Median of the two sorted arrays is " + median);
}
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int[] merged = new int[m + n]; // merged array
int i = 0, j = 0, k = 0;
// Merge the two sorted arrays into a single sorted array
while (i < m && j < n) {
if (nums1[i] <= nums2[j]) {
merged[k++] = nums1[i++];
} else {
merged[k++] = nums2[j++];
}
}
while (i < m) {
merged[k++] = nums1[i++];
}
while (j < n) {
merged[k++] = nums2[j++];
}
// Find the median of the combined set
if ((m + n) % 2 == 0) {
int mid = (m + n) / 2;
return (double) (merged[mid - 1] + merged[mid]) / 2;
} else {
int mid = (m + n) / 2;
return (double) merged[mid];
}
}
}
Output:
Median of the two sorted arrays is 5.0
Complexity Analysis:
The time complexity of the findMedianSortedArrays
method is O(m + n), where m and n are the lengths of the two input arrays. we need to iterate through both arrays to merge them into a single sorted array.
The space complexity of the findMedianSortedArrays
method is O(m + n), where m and n are the lengths of the two input arrays. we are creating a new array to store the merged array. The space complexity does not increase with the input size, making it a constant space complexity algorithm.
Approach 2: Using Recursion
The idea behind the recursive approach is to divide the arrays into two parts such that the number of elements in each part is equal (or differs by one). Then, we can compare the middle elements of the two parts to determine the median. If the middle elements are equal, then we have found the median. Otherwise, we can discard the part of the array that contains the smaller middle element and the part of the array that contains the larger middle element. We repeat this process until we find the median.
Program:
FileName: MedianOfTwoSortedArrays.java
import java.util.*;
public class MedianOfTwoSortedArrays {
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n1 = nums1.length;
int n2 = nums2.length;
// ensure that nums1 is the smaller array
if (n1 > n2) {
return findMedianSortedArrays(nums2, nums1);
}
// if nums1 is empty, the median is the middle element of nums2
if (n1 == 0) {
return (double) (nums2[(n2-1)/2] + nums2[n2/2]) / 2.0;
}
int low = 0, high = n1;
while (low <= high) {
int partition1 = (low + high) / 2;
int partition2 = (n1 + n2 + 1) / 2 - partition1;
// calculate the maximum value on the left side of partition in nums1
int maxLeft1 = (partition1 == 0) ? Integer.MIN_VALUE : nums1[partition1-1];
// calculate the minimum value on the right side of partition in nums1
int minRight1 = (partition1 == n1) ? Integer.MAX_VALUE : nums1[partition1];
// calculate the maximum value on the left side of partition in nums2
int maxLeft2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2[partition2-1];
// calculate the minimum value on the right side of partition in nums2
int minRight2 = (partition2 == n2) ? Integer.MAX_VALUE : nums2[partition2];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
// we have found the median
if ((n1 + n2) % 2 == 0) {
return (double) (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;
} else {
return (double) Math.max(maxLeft1, maxLeft2);
}
} else if (maxLeft1 > minRight2) {
// we need to move partition1 to the left
high = partition1 - 1;
} else {
// we need to move partition1 to the right
low = partition1 + 1;
}
}
// we should never get here
return -1;
}
public static void main(String[] args) {
int[] nums1 = {1, 3, 5, 7, 9};
int[] nums2 = {2, 4, 6, 8, 10, 12};
double median = findMedianSortedArrays(nums1, nums2);
System.out.println("Median = " + median);
}
}
Output:
Median = 6.0
Complexity Analysis:
Time Complexity: The time complexity of the findMedianSortedArrays
method is O(log(min(m, n))), where m and n are the lengths of the input arrays. Here we are dividing the smaller array into two parts using binary search, which takes O(log(min(m, n))) time. Since we are only performing a constant amount of work at each step, the overall time complexity is O(log(min(m, n))).
Space Complexity: The space complexity of the findMedianSortedArrays
method is O(1), as we are not using any extra space besides a few variables to store the indices and values of the input arrays. Therefore, the space complexity is constant and does not depend on the size of the input arrays.
Approach 3: Using BinarySearch
Program:
File Name: MedianOfTwoSortedArrays
import java.util.*;
public class MedianOfTwoSortedArrays {
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n1 = nums1.length;
int n2 = nums2.length;
// ensure that nums1 is the smaller array
if (n1 > n2) {
return findMedianSortedArrays(nums2, nums1);
}
int low = 0, high = n1;
while (low <= high) {
int partition1 = (low + high) / 2;
int partition2 = (n1 + n2 + 1) / 2 - partition1;
// calculate the maximum value on the left side of partition in nums1
int maxLeft1 = (partition1 == 0) ? Integer.MIN_VALUE : nums1[partition1-1];
// calculate the minimum value on the right side of partition in nums1
int minRight1 = (partition1 == n1) ? Integer.MAX_VALUE : nums1[partition1];
// calculate the maximum value on the left side of partition in nums2
int maxLeft2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2[partition2-1];
// calculate the minimum value on the right side of partition in nums2
int minRight2 = (partition2 == n2) ? Integer.MAX_VALUE : nums2[partition2];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
// we have found the median
if ((n1 + n2) % 2 == 0) {
return (double) (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;
} else {
return (double) Math.max(maxLeft1, maxLeft2);
}
} else if (maxLeft1 > minRight2) {
// we need to move partition1 to the left
high = partition1 - 1;
} else {
// we need to move partition1 to the right
low = partition1 + 1;
}
}
// we should never get here
return -1;
}
public static void main(String[] args) {
int[] nums1 = {1, 3, 5, 7, 9};
int[] nums2 = {2, 4, 6, 8, 10, 12};
double median = findMedianSortedArrays(nums1, nums2);
System.out.println("Median = " + median);
}
}
Output:
Median = 6.0
Complexity Analysis:
Time Complexity: The time complexity of the findMedianSortedArrays
method is O(log(min(m, n))), where m and n are the lengths of the input arrays. Here we are dividing the smaller array into two parts using binary search, which takes O(log(min(m, n))) time. Since we are only performing a constant amount of work at each step, the overall time complexity is O(log(min(m, n))).
Space Complexity: The space complexity of the findMedianSortedArrays
method is O(1), as we are not using any extra space besides a few variables to store the indices and values of the input arrays. Therefore, the space complexity is constant and does not depend on the size of the input arrays.
Approach 4:Using Priority Queue
We can use a priority queue to merge the two sorted arrays into a single sorted array. The priority queue can be implemented using a heap data structure, where the top element of the heap is always the smallest element. We can add all the elements of both arrays to the priority queue, and then repeatedly remove the smallest element from the queue until we reach the middle element(s) of the merged array. If the merged array has an odd number of elements, then the middle element is the median. If the merged array has an even number of elements, then the median is the average of the middle two elements.
Program:
FileName: MedianOfTwoSortedArrays
import java.util.PriorityQueue;
public class MedianOfTwoSortedArrays {
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
// initialize priority queue
PriorityQueue<Integer> pq = new PriorityQueue<>();
// add all elements to priority queue
for (int i = 0; i < nums1.length; i++) {
pq.offer(nums1[i]);
}
for (int i = 0; i < nums2.length; i++) {
pq.offer(nums2[i]);
}
int n = nums1.length + nums2.length;
// remove elements until we reach the middle element(s)
for (int i = 0; i < n/2; i++) {
pq.poll();
}
if (n % 2 == 0) {
// average of middle two elements
int a = pq.poll();
int b = pq.poll();
return (a + b) / 2.0;
} else {
// middle element
return pq.poll();
}
}
public static void main(String[] args) {
int[] nums1 = {1, 3, 5, 7, 9};
int[] nums2 = {2, 4, 6, 8, 10, 12};
double median = findMedianSortedArrays(nums1, nums2);
System.out.println("Median = " + median);
}
}
Output:
Median = 6.0
Complexity Analysis:
The time complexity of the findMedianSortedArrays
method using a priority queue is O((m+n) log(m+n)), where m and n are the lengths of the input arrays. Here we are adding all the elements of both arrays to the priority queue, which takes O(m+n) time. Then we are removing the middle element(s) from the queue, which takes O((m+n) log(m+n)) time, as each removal operation takes O(log(m+n)) time. Therefore, the overall time complexity is O((m+n) log(m+n)).
Space Complexity:
The space complexity of the findMedianSortedArrays
method using a priority queue is O(m+n), as we are using a priority queue to store all the elements of both arrays. Therefore, the space complexity is proportional to the size of the input arrays.