Median of Two Sorted Arrays

Difficulty Level Hard
Frequently asked in Adobe Amazon Apple Bloomberg ByteDance Facebook Goldman Sachs Google Microsoft Wish
Array Binary Search Divide and ConquerViews 1588

Given two sorted arrays A and B of size n and m respectively. Find the median of the final sorted array obtained after merging the given two arrays or in other words, we say that find median of two sorted arrays.

( Expected time complexity: O(log(n)) )

Approach 1 for Median of Two Sorted Arrays

Using the two-pointer method, create a merged sorted array of A and B.

Then simply find the median of that array.

C++ Program for Median of Two Sorted Arrays

#include<bits/stdc++.h>
using namespace std;
double findMedian(int A[],int B[],int n,int m){
    int k=n+m;                   // size of merged sorted array
    int M[k];                   // array which will store integers of A and B in ascending order
    int i=0,j=0,in=0;          // i is a pointer index for A
                              // j is a pointer index for B 
                             // in is a pointer index for M
    while(i<n || j<m){
        if(i<n && j<m){
            if(A[i]<B[j]){
                M[in]=A[i];
                i++;
            }
            else{
                M[in]=B[j];
                j++;
            }
        }
        else{
            if(i<n){
                M[in]=A[i];
                i++;
            }
            else{
                M[in]=B[j];
                j++;
            }
        }
        in++;
    }
    if(k%2==0){
        double m1 = M[k/2];
        double m2 = M[(k/2)-1];
        return (m1+m2)/2;
    }
    else{
        double m1 = M[k/2];
        return m1;
    }
    return -1;    
}
int main(){
    int n,m;
    cin>>n>>m;
    int A[n],B[m];
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    for(int i=0;i<m;i++){
        cin>>B[i];
    }
    double median = findMedian(A,B,n,m);
    cout<<median<<"\n";
}
5 5
6 1 2 7 8
3 4 5 6 7
3.5

Complexity Analysis

Time Complexity: O(max(n,m) because we find the merging sorted array by using the both arrays.

Space Complexity: O(n+m) because we store the final merged array that will lead us to O(n+m) space complexity.

Approach 2 for Median of Two Sorted Arrays

To solve this problem, we need to first understand what actually does the median do.

It is the partitioning of set into two equal length subsets such that one subset is greater than the other.

i.e., partition the set into two subsets such that every element of one subset is greater than every element of the other subset.

Now come back to the problem, we need to find the median of two sorted arrays.

Can we find a partition for array A and B, such that the length of subsets obtained by adding left of both partitions and right of both partitions are equal?

Median of Two Sorted Arrays

 

Partitioning an array at the ith position also denotes the number of elements from that array that are present in the left subset.

And as we know that the length of subsets obtained should be equal, hence

partitionA + partitionB = (length(A) +length(B)+1)/2

(If the length of the final merged sorted array is odd then, left subset would have more elements)

Now the only thing left is to check how to partition the given two arrays such that the right subset is greater than the left subset.

Let’s define the perfect partition of sorted arrays:

Let say we have array A( length n) and an array B( length m )

Median of Two Sorted Arrays

 

We have partitioned A at i and B at j, then

A perfect partition is when:

  • i+j = (n+m+1)/2 (subsets are of equal length)
  • A[i-1]<=B[j] (elements of A in the left of i will come in the left subset)
  • B[j-1]<=A[i] (elements of B in the left of j will come in left subset)

If A[i-1]>B[j] that means there are some elements in the left of A’s partition that should be placed in the greater(right) subset. In that case, we will move i towards left and j towards the right.

If B[j-1]>A[i] that means there are some elements in the left of B’s partition which should be placed in the greater(right) subset. In that case, we will move j towards the left and i toward the right.

Now to move our partition pointers we can use binary search.

Explanation

Let’s understand it with an example:

Given two sorted arrays A and B.

Let’s start partitioning A using binary search and check if we can get a perfect partition or not.

Step 1

left=0

right=6

mid=(0+6)/2 = 3   (partition for A)

We can get the partition of B using partitionA + partitionB = (length(A) +length(B)+1)/2

partitionB= (6+4+1)/2  – partitionA

partitionB = 5-3 = 2

Left of B’s partition is greater than right of A’s partition. This means we have to add more elements of A for perfect partition.

Step 2

Do left=mid+1 i.e., left = 4

right=6

hence new mid = (4+6)/2 =5

partitionB  =(6+4+1)/2 – partitionA

partitionB = 0

As left of A’s partition is greater than right of B’s partition. This means we should add more elements of B to get perfect partition.

Step 3

Do right = mid-1

Left = 4

right = 4

hence new mid = (4+4)/2 = 4

partitionB= (6+4+1)/2 – partitionA

partitionB = 1

Now we can see there are total 5 elements in the enclosed figure and total 5 elements outside it.

Also, the left of A’s partition is less than the right of B’s partition.

And the left of B’s partition is less than the right of A’s partition.

Hence our array will merge like this:

As our array is of even size hence the median will be obtained by taking average of middle two elements of final sorted array:

  • One will be the maximum of the left side of perfect partition i.e., max(17,11).
  • The second will be the minimum of the right side of perfect partition i.e., min(19,18).

Isn’t it?

Median obtained = (17+18)/2

= 17.5

If the length of the merged sorted array is odd, then the answer will simply be the maximum of the left side of the perfect partition.

Example

Input:

The first line of input contains two integers n and m, denoting the size of array A and B.

The next line contains n space-separated integers which denote A[i] where 0<=i<n.

The next line contains m space-separated integers which denote B[i] where 0<=i<m.

Output:

Print the median of given two sorted arrays.

C++ Program for Median of Two Sorted Arrays

#include<bits/stdc++.h>
using namespace std;
double findMedian(int A[],int B[],int n,int m){
    int left = 0, right = n;
    while (left <= right) {
        int partitionA = (left + right)/2;
        int partitionB = (n + m + 1)/2 - partitionA;      // partitionA + partitionB = (n+m+1)/2

        //if partitionA is 0 then take INT_MIN for maxLeftA (nothing is left in the left of partition)
        double maxLeftA = INT_MIN;
        if(partitionA > 0){
            maxLeftA = A[partitionA-1];
        }
            
        //if partitionA is n then take INT_MAX for minRightA (nothing is left in the right of partition)
        double minRightA = INT_MAX;
        if(partitionA < n){
            minRightA = A[partitionA];
        }
        
        //Similarly for maxLeftB and minrightB
        double maxLeftB = INT_MIN;
        if(partitionB > 0){
            maxLeftB = B[partitionB-1];
        }
            
        double minRightB = INT_MAX;
        if(partitionB < m){
            minRightB = B[partitionB];
        }
        if (maxLeftA <= minRightB && maxLeftB <= minRightA) {     // check weather it's a perfect partition or not
            if ((n+m) % 2 == 0) {                                // if the sorted merged array is of even length
                return (max(maxLeftA, maxLeftB) + min(minRightA, minRightB))/2;
            } 
            else {
                return max(maxLeftA, maxLeftB);
            }
        } 
        else if (maxLeftA > minRightB) {                          //move left side.
            right = partitionA - 1;
        }
        else {                                                   // move right side
            left = partitionA + 1;
        }
    }
    return -1;    // we can't find the median if input is invalid i.e., arrays are not sorted
}
int main(){
    int n,m;
    cin>>n>>m;
    int A[n],B[m];
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    for(int i=0;i<m;i++){
        cin>>B[i];
    }
    double median = findMedian(A,B,n,m);
    cout<<median<<"\n";
}
4 5
1 2 7 8
3 4 5 6 7
5

JAVA Program for Median of Two Sorted Arrays

import java.util.Scanner;
public class Main{
    public static double findMedian(int A[], int B[],int n,int m) {
        int left = 0, right = n;
        while (left <= right) {
            int partitionA = (left + right)/2;
            int partitionB = (n + m + 1)/2 - partitionA;      // partitionA + partitionB = (n+m+1)/2
            //if partitionA is 0 then take INT_MIN for maxLeftA (nothing is left in the left of partition)
            double maxLeftA = Integer.MIN_VALUE;
            if(partitionA > 0){
                maxLeftA = A[partitionA-1];
            }
                
            //if partitionA is n then take INT_MAX for minRightA (nothing is left in the right of partition)
            double minRightA = Integer.MAX_VALUE;
            if(partitionA < n){
                minRightA = A[partitionA];
            }
                
            //Similarly for maxLeftB and minrightB
            double maxLeftB = Integer.MIN_VALUE;
            if(partitionB > 0){
                maxLeftB = B[partitionB-1];
            }
                    
            double minRightB = Integer.MAX_VALUE;
            if(partitionB < m){
                minRightB = B[partitionB];
            }
            if (maxLeftA <= minRightB && maxLeftB <= minRightA) {     // check weather it's a perfect partition or not
                if ((n+m) % 2 == 0) {                                // if the sorted merged array is of even length
                    return (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB))/2;
                } 
                else {
                    return Math.max(maxLeftA, maxLeftB);
                }
            } 
            else if (maxLeftA > minRightB) {                          //move left side.
                right = partitionA - 1;
            }
            else {                                                   // move right side
                left = partitionA + 1;
            }
        }
        return -1;    // we can't find the median if input is invalid i.e., arrays are not sorted
    }
        
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n,m;
        n = scan.nextInt();
        m = scan.nextInt();
        int A[]=new int[n];
        int B[]=new int[m];
        for(int i=0;i<n;i++){
            A[i] = scan.nextInt();
        }
        for(int i=0;i<m;i++){
            B[i] = scan.nextInt();
        }
        double median = findMedian(A,B,n,m);
        System.out.println(median);  
    }
}
4 6
6 7 8 9
1 2 3 4 5 6
5.5

Complexity Analysis for Median of Two Sorted Arrays

Time Complexity: O(log(n))

as at every step, we are reducing the search space by half (either choosing left search space or right search space from the middle index).

Space Complexity: O(1) because we just use some variables for calculation.

Thanks for reading!!

References

Translate »