Table of Contents
Problem statement
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Example
Example 1:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
JAVA CODE Median of Two Sorted Arrays
BRUTE FORCE APPROACH
LOGIC
- Merge 2 arrays by traversing 2 given array in 3rd array i.e. result.
- Find median from result array and return.
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int length1 = nums1.length, length2 = nums2.length;
int[] result = new int[length1 + length2];
double median = 0.0;
int index1 = 0, index2 = 0, index3 = 0;
while (index1 < length1 && index2 < length2) {
if (nums1[index1] < nums2[index2]){
result[index3] = nums1[index1];
index1++;
index3++;
}else{
result[index3] = nums2[index2];
index2++;
index3++;
}
}
while (index1 < length1){
result[index3] = nums1[index1];
index1++;
index3++;
}
while (index2 < length2){
result[index3] = nums2[index2];
index2++;
index3++;
}
if ((length1 + length2) % 2 == 0){
median = ((double)(result[index3/2]) + (double)(result[(index3/2)-1])) / (double)(2.0);
} else {
median = (double)(result[index3/2]);
}
return median;
}
}Better Approach
LOGIC
- We need only 2 value median_value_1 and median_value_2 to find out median.
- We DO NOT need to save entire 3rd result array.
- We can keep track of counter while comparing in above brute force code, once it reaches (total/2) OR (total/2)-1 index value, we will save them.
- Another thing, we can do, as soon as it reached total/2, we can break out of the loop and return median directly using median formula.
- This will save execution time for rest of the total/2 numbers comparison.
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int length1 = nums1.length, length2 = nums2.length;
int total = length1 + length2;
double median = 0.0;
int median_value_1 = 0, median_value_2 = 0;
int index1 = 0, index2 = 0, counter = 0;
while (index1 < length1 && index2 < length2) {
if (nums1[index1] < nums2[index2]){
if (counter == total/2) {
median_value_1 = nums1[index1];
}else if (counter == (total/2)-1){
median_value_2 = nums1[index1];
}
index1++;
counter++;
}else{
if (counter == total/2) {
median_value_1 = nums2[index2];
}else if (counter == (total/2)-1){
median_value_2 = nums2[index2];
}
index2++;
counter++;
}
}
while (index1 < length1){
if (counter == total/2) {
median_value_1 = nums1[index1];
}else if (counter == (total/2)-1){
median_value_2 = nums1[index1];
}
index1++;
counter++;
}
while (index2 < length2){
if (counter == total/2) {
median_value_1 = nums2[index2];
}else if (counter == (total/2)-1){
median_value_2 = nums2[index2];
}
index2++;
counter++;
}
if (total % 2 == 0){
median = (median_value_1 + median_value_2) / (double)(2.0);
} else {
median = (double)(median_value_1);
}
return median;
}
}Optimal Solution
Logic
- We have to divide small array such that there will 2 partition partitionX in smaller array & partitionY in bigger array.
- Then we will check if all elements on the left hand side of partition are smaller than all elements on the right hand side both partition.
- We can do this simply by checking below condition
- (maxLeftX <= minRightY && maxLeftY <= minRightX)
- maxLeftX is the maximum element on the left hand side & minRightX is the minimum element on the right hand side of smaller array.
- similarly, we will define minRightY and maxLeftY for bigger array.
- To handle edge case, we we are at the boundary, we will use Integer.MIN_VALUE and Integer.MAX_VALUE as -INFINITY, +INFINITY.
Complexity
- Time Complexity : O(log(min(x,y)))
- That log of number of elements in smaller array.
- Space Complexity : O(1)
- No extra space used.
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 1. find smallest array
if (nums1.length > nums2.length){
return findMedianSortedArrays(nums2, nums1);
}
// 2. traverse over smaller array
int x = nums1.length;
int y = nums2.length;
int maxLeftX, maxLeftY, minRightX, minRightY;
int low = 0;
int high = x;
while (low <= high) {
// partitionX + partitionY = (x + y + 1) / 2;
int partitionX = (low + high) / 2;
int partitionY = ((x + y + 1) / 2) - partitionX;
maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX-1];
minRightX = (partitionX == x) ? Integer.MAX_VALUE: nums1[partitionX];
maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY-1];
minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];
// 3. logic
if (maxLeftX <= minRightY && maxLeftY <= minRightX){
if ((x+y) % 2 == 0){
return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / (double)(2.0);
} else {
return (double)(Math.max(maxLeftX, maxLeftY));
}
} else if (maxLeftX > minRightY) {
// shift towards left
high = partitionY - 1;
} else {
// shift towards right
low = partitionX + 1;
}
}
throw new IllegalArgumentException();
}
}Visit https: https://codeandalgo.com for more such contents.
Leave a Reply