Median of Two Sorted Arrays

Problem :

Given two sorted arrays find the median of the sorted arrays when merged.

Find a solution in less than O(n) time complexity where n is the length of the merged array.

Also don’t use extra space – Space complexity should be O(1)

What is median?

Median is the middlemost element of a sorted array if the length of the array is odd.

It is the average of the middle two elements of a sorted array if the length is even.

For example,

Median of [1,2,3] is 2

Median of [1,2,3,4] is (2+3)/2 which is 2.5

Now let’s go back to the problem.

Here is a sample input:

nums1 = [1,4,8]

nums2 = [2,3,7,9]

If the above two arrays are merged then the merged array would be :

[1,2,3,4,7,8,9]

So median is 4 (middle element since the length of the array is odd)

Try out the solution here:

https://leetcode.com/problems/median-of-two-sorted-arrays

Solution:

Approach 1 – Use extra space and O(n) time complexity

We want to solve this problem in less than O(n) time complexity and in O(1) space complexity.

But first let’s see how to solve this in O(n) time complexity using extra space O(n)

Here n denotes the combined space of the two arrays.

In this approach ,

We will create a new array with the combined size of both the arrays.

We will then use two pointers.

The first pointer points to the first element in the first array.

And the second pointer points to the first element in the second array.

We will compare each element pointed to by the two pointers.

Whichever is smaller we will put that element in the merged array and increment the corresponding pointer.

If one of the arrays is smaller in length then it will get exhausted first.

We just need to copy the remaining elements of the other array into the merged array.

Our merged array is now ready.

Now we need to find the median .

Return the middle element if the size is odd.

Return the average of the middle two elements if the size is even.

Here is the code:

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {


int firstlen = nums1.length;
int secondlen = nums2.length;
int finallen = firstlen+secondlen;

int[] merged = new int[finallen];


int pointer1 = nums1.length >0 ? 0 : -1;
int pointer2 = nums2.length > 0 ? 0 : -1;
 

int index = 0;

 while(pointer1 != -1 && pointer1 < firstlen && pointer2 != -1 && pointer2 <secondlen){


     if(nums1[pointer1] < nums2[pointer2]){

         merged[index++] = nums1[pointer1];
        pointer1++;

     }else{

         merged[index++] = nums2[pointer2];
         pointer2++;
     }
 }

    while(pointer1 < firstlen && pointer1 != -1){


        merged[index++] = nums1[pointer1++];
    }

    while(pointer2 < secondlen && pointer2 != -1){

        merged[index++] = nums2[pointer2++];
    }
   


     if(finallen % 2 ==0) return (merged[finallen/2] + merged[(finallen/2) - 1] )/2.0;


     return merged[finallen/2];


    }
}

Approach 2 :

In this approach we are going to make use of binary search.

We are not going to use additional memory in proportion to the input.

Also we are not going to check all the elements in the two arrays!

How can we do this?

Notice that in a sorted merged array ,

All the elements in the left half are lesser than the elements in the right half

We are going to make use of this and dig further.

So if we can find the two halves without actually merging the array we can find the median.

Also notice that you don’t really need to find all the elements of the two halves.

You need to know only the last element in the first half and the first element in the second half (for even sized merged array )

So we need to find :

The last element in the first array and the first element in the second array

Now how do we find this?

We are going to follow a kind of greedy approach.

We will split the two arrays into two .

We will keep splitting them until we get the required halves.

In the final halves,

The left split of the first array and the left split of the second array will together represent the left half of the final merged array.

Similarly,

The right split of the first array and the right split of the second array will together represent the right half of the final merged array.

For example,

Given the input

[1,2]

[4,6,12,17]

First array has 2 elements.

Second array has 4 elements.

So in the final merged array there will be 6 elements with 3 elements in the left half and 3 elements in the right half.

We need to find these 3 elements in each half.

For this we will cut the first array at some point less than or equal to 3 .

Let’s say we make a cut at the position 1.

So the array [1,2] gets split into two.

We will pick the element left to this cut which is 1.

Now we have got one element for our left half.

We need 2 more elements for the left half of the final merged array.

So we will take the remaining 2 from the second array.

We will make a cut in the second array too:

Now we have got 3 elements in the left half and 3 elements in the right half along the two cuts:

Let’s represent the left split of the first array as l1,

the left split of the second array as l2,

the right split of the first array as r1,

the right split of the second array as r2.

Now it is obvious that l1 is less than r1 and l2 is less than r2 since the arrays are sorted.

Now if we can confirm that l1 is less than r2 and l2 is less than r1 then we know that the combined left half l1 and l2 is less than the combined right half r1 and r2.

To check this we just need to check the last element of l1 with the first element of r2.

And check the last element of l2 with the first element of r1.

But in the above case that is not the case.

l1 = 1 , r1 = 2

l2 = 6 , r2 = 12

l1is less than r2

But l2 is not less than r1

So we move our first cut to the right by one position.

Whenever we move right in the first array we need to move left in the left array to keep the number of elements in balance.

So let’s do it:

Now l1 = 2, l2 = 4 , r2 = 6

We don’t have any element in the right split of the first array.

In this case we can assume the maximum element there .

So let’s consider infinity.

Now r1 = infinity.

So l1 < r2 and l2 < r1

The conditions are matched!

We have got our left half and right half of the merged array.

Now let’s find the median

To find the median for an even sized sorted array we need two middle elements.

one is from the left half

another is from the right half.

The one from the left half should be the maximum element in the left half.

And the one from the right half should be the minimum element in the right half.

So we will choose the maximum of l1 and l2 and the minimum of r1 and r2 and find their average.

Median = Max(l1,l2) + Min(r1,r2) / 2 = Max (2,4) + Min (infinity,6) /2 = (4 + 6 )/2 = 5

In case of an odd sized array, the median element is the middle element.

It will be the maximum element in the left half.

Median = Max (l1,l2)

To note:

We make the first cut in the first array and make the second cut accordingly in the second array.

So let us choose the smaller one as the first array.

This will help us in avoiding few boundary checks and improve time complexity since we will be doing binary search only in the first array.

Here is the algorithm:

1. Check the size of the arrays
2. If first array is bigger than the second array swap the arrays
3. Make the first cut at half the position of the first array
4. Find the middle position of the final merged array
5. When the first cut is within the first array boundaries do the following :
   • Find the second cut
   • Based on the first cut find the first left l1 (one element to the left of the cut)
   • Based on the second cut find the second left l2(one element to the left of the right cut)
   • Based on the first cut find the first right r1(element at the position of the first cut)
   • Based on the second cut find the second right r2(element at the position of the second cut)
   • Check if l1<=r2 and l2<=r1 , If yes we have found the left and right halves
     • Find the median
   • If l1 > r2 , move the first cut left by one position
   • If l2 > r1 , move the first cut right by one position
6. If no median could be found return 0

Here is the code :

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {


        int firstlen = nums1.length;

        int secondlen = nums2.length;

        


        if(firstlen > secondlen) {

           return findMedianSortedArrays(nums2,nums1);
        }

   

      
            int cut1 = firstlen /2;

          
            int midOfMergedArray = ( (firstlen+secondlen+1) / 2 );


        while(cut1 >=0 && cut1 <= firstlen){
     

             int cut2 = midOfMergedArray - cut1;


            int l1 = (cut1 == 0) ? Integer.MIN_VALUE : nums1[cut1-1];
            int l2 = (cut2 == 0 )? Integer.MIN_VALUE: nums2[cut2 -1];

            int r1 = (cut1 == firstlen) ? Integer.MAX_VALUE: nums1[cut1];
            int r2 = (cut2 == secondlen) ? Integer.MAX_VALUE : nums2[cut2];


             if(l1 <= r2 && l2 <= r1){

                   if( (firstlen+secondlen) % 2 ==0 ) return (Math.max(l1,l2) +Math.min(r1,r2)) /2.0;


                   return Math.max(l1,l2);


         }else if(l1 > r2){

            cut1 = cut1 - 1;

         }else{

             cut1 = cut1 + 1;
         }


        }


        return 0;
    }
}

Time complexity:

We are doing a binary search in the smaller array and making a cut accordingly in every iteration.

So time complexity is O(log (min(m,n)) where m and n are sizes of the two arrays.

min – minimum

Space complexity:

We are not using any extra space so space complexity is O(1)

That’s it!