### Median of Two Sorted Arrays Java Program - The Coding Shala

Home >> Interview Questions >> Median of two sorted arrays

## Median of Two Sorted Arrays Java Program

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1,2]

nums2 = [3,4]

The median is 2.5.

Example 2

nums1 = [3]

nums2 = [-1, -2]

The median is -2.

### Median of Two Sorted Arrays Java Program

Before solving this we'll see what is median and how to find it. So basically a median is the value present at the center of a sorted array. Now the length of the array can be odd or even.
let's solve the median of two sorted arrays.

Method 1:
We have two sorted arrays, now if we merge both arrays into one(still sorted) then we can easily find the center of the merged array, But this method takes O(n+m) time and O(n+m) extra space. here n and m are lengths of given arrays. This is a simple approach to solve this problem. Let's code it first using this method then we will solve it in a log(m+n) time.

Java Code:

```class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
double ans = 0;
int len1 = nums1.length;
int len2 = nums2.length;
int[] arr = new int[len1+len2];
int i=0, j=0,k=0;
while(i<len1 && j<len2){
if(nums1[i]<=nums2[j]){
arr[k] = nums1[i];
i++;
k++;
}else{
arr[k] = nums2[j];
k++;
j++;
}
}
while(i<len1){
arr[k] = nums1[i];
i++;
k++;
}
while(j<len2){
arr[k] = nums2[j];
j++;
k++;
}
int len = arr.length;
if(len%2 != 0) ans = (double)arr[len/2];
else{
ans = (double)(arr[(len-1)/2] + arr[(len/2)])/2;
}
return ans;
}
}
```

Method 2:
Time Complexity: O(log(m+n)).
Space Complexity: O(1).

The median is used for dividing a set into two equals subsets that one subset is always greater than the others.

Now let's take an example of how to solve this problem in log(m+n) time.

We have two sorted arrays A and B.
First, let's cut array A[] into two parts at a random position i.
Here, the size of A[] is m so we can make m+1 cuts(i=0 to m). When i=0 left_A is empty and when i=m, right_A is empty.
Now the same way we cut B[] into two parts at a random position j.
As a next step, we will put left_A and left_B into one set and put right_A and right_B into another set.
When we find such a cut where

A[i-1] <= B[ j ] and,
B[ j-1 ] <= A[i]

and exactly we need to find this condition. We will return the median of two sorted arrays using these four elements.

The median is:
We will use a binary search to find these cuts(partitions).
Note: take m<n.

How will we make these cuts(partitions)? Take two variables min_index and max_index and initialize min_index to 0 and max_index to m(length of the smaller array).

To Partition A[], use formula (min_index + max_index)/2 and insert it to i(mid for A[]).

To partition B[], use the formula (n+m+1)/2 - i and insert in to a variable j(mid for B[]).

Now, let's take an example first to understand this approach:

we have two arrays:
A[] = {3,5,10,11,17}
B[] = {9, 13, 20, 21, 23, 27}
After the first iteration:
here, condition is not satisfies so move forward and set min_index to i+1.

second iteration:
here, condition is satisfied so (n+m) = (5+6) is 11 is odd length, median is max(11,13) is 13.

Now let's code it.

Java Code:

```class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;

//take smaller array first
if(m>n) return findMedianSortedArrays(nums2, nums1);

int i=0,j=0; //for mid point
int min_index = 0;
int max_index = m;
int half = (m+n+1)/2;
//binary search
while(min_index <= max_index){
//mid for first array
i = (min_index+max_index)/2;
//mid for second array
j = half-i;

//move min_index to mid+1
if(i<m && j>0 && (nums1[i]<nums2[j-1])) min_index = i+1;
//move max_index to mid-1
else if(i>0 && j<n && (nums1[i-1]>nums2[j])) max_index = i-1;
else{
//here our condition matched
//nums1[i-1]<=nums2[j]
//and
//nums2[j-1]<=nums1[i]
break;
}
}

//find out max of left half
int max_left = 0;
if(i==0) max_left = nums2[j-1];
else if(j==0) max_left = nums1[i-1];
else{
max_left = Math.max(nums1[i-1], nums2[j-1]);
}

if((m+n)%2 !=0){
//median is max of first half
//*1.0 for double
return max_left*1.0;
}

//find min of right half
int min_right = 0;
if(i==m) min_right = nums2[j];
else if(j==n) min_right = nums1[i];
else{
min_right = Math.min(nums1[i], nums2[j]);
}
//case 2 m+n is even length
//median is avergae of max first half and min second half
return (max_left+min_right)/2.0;
}
}
```

Other Posts You May Like