### 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**

## Comments

## Post a Comment