Open In App

Median of two Sorted Arrays of Different Sizes

Last Updated : 02 May, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

Given two sorted arrays, a[] and b[], the task is to find the median of these sorted arrays, where N is the number of elements in the first array, and M is the number of elements in the second array. 

This is an extension of Median of two sorted arrays of equal size problem. Here we handle arrays of unequal size also.

Examples: 

Input: a[] = {-5, 3, 6, 12, 15}, b[] = {-12, -10, -6, -3, 4, 10}
Output: The median is 3.
Explanation: The merged array is: ar3[] = {-12, -10, -6, -5 , -3, 3, 4, 6, 10, 12, 15}.
So the median of the merged array is 3

Input: a[] = {2, 3, 5, 8}, b[] = {10, 12, 14, 16, 18, 20}
Output: The median is 11.
Explanation : The merged array is: ar3[] = {2, 3, 5, 8, 10, 12, 14, 16, 18, 20}
If the number of the elements are even. So there are two middle elements.
Take the average between the two: (10 + 12) / 2 = 11.

Naive Approach to find Median of two sorted Arrays of different sizes

The idea is to merge them into third array and there are two cases:

  • Case 1: If the length of the third array is odd, then the median is at (length)/2th index in the array obtained after merging both the arrays.
  • Case 2: If the length of the third array is even, then the median will be the average of elements at index ((length)/2 ) and ((length)/2 – 1) in the array obtained after merging both arrays.

Illustration:

arr1[] = { -5, 3, 6, 12, 15 } , arr2[] = { -12, -10, -6, -3, 4, 10 }

  • After merging them in a third array : arr3[] = { -5, 3, 6, 12, 15, -12, -10, -6, -3, 4, 10}
  • Sort arr3[ ] = { -12, -10, -6, -5, -3, 3, 4, 6, 10, 12, 15 }
  • As the length of arr3 is odd, so the median is 3

Below is the implementation of the above approach:

C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;

int Solution(int arr[], int n)
{

    // If length of array is even
    if (n % 2 == 0) {
        int z = n / 2;
        int e = arr[z];
        int q = arr[z - 1];
        int ans = (e + q) / 2;
        return ans;
    }

    // If length if array is odd
    else {
        int z = round(n / 2);
        return arr[z];
    }
}

// Driver Code
int main()
{
    int arr1[] = { -5, 3, 6, 12, 15 };
    int arr2[] = { -12, -10, -6, -3, 4, 10 };

    int i = sizeof(arr1) / sizeof(arr1[0]);
    int j = sizeof(arr2) / sizeof(arr2[0]);

    int arr3[i + j];
    int l = i + j;
    // Merge two array into one array
    for (int k = 0; k < i; k++) {
        arr3[k] = arr1[k];
    }

    int a = 0;
    for (int k = i; k < l; k++) {
        arr3[k] = arr2[a++];
    }

    // Sort the merged array
    sort(arr3, arr3 + l);

    // calling the method
    cout << "Median = " << Solution(arr3, l);
}

// This code is contributed by SoumikMondal
Java
// Java program for the above approach
import java.io.*;
import java.util.Arrays;

public class GFG {
    public static int Solution(int[] arr)
    {
        int n = arr.length;

        // If length of array is even
        if (n % 2 == 0) {
            int z = n / 2;
            int e = arr[z];
            int q = arr[z - 1];

            int ans = (e + q) / 2;
            return ans;
        }

        // If length if array is odd
        else {
            int z = Math.round(n / 2);
            return arr[z];
        }
    }

    // Driver Code
    public static void main(String[] args)
    {
        int[] arr1 = { -5, 3, 6, 12, 15 };
        int[] arr2 = { -12, -10, -6, -3, 4, 10 };

        int i = arr1.length;
        int j = arr2.length;

        int[] arr3 = new int[i + j];

        // Merge two array into one array
        System.arraycopy(arr1, 0, arr3, 0, i);
        System.arraycopy(arr2, 0, arr3, i, j);

        // Sort the merged array
        Arrays.sort(arr3);

        // calling the method
        System.out.print("Median = " + Solution(arr3));
    }
}
// This code is contributed by Manas Tole
Python3
# Python3 program for the above approach
def Solution(arr):

    n = len(arr)

    # If length of array is even
    if n % 2 == 0:
        z = n // 2
        e = arr[z]
        q = arr[z - 1]
        ans = (e + q) / 2
        return ans

    # If length of array is odd
    else:
        z = n // 2
        ans = arr[z]
        return ans


# Driver code
if __name__ == "__main__":

    arr1 = [-5, 3, 6, 12, 15]
    arr2 = [-12, -10, -6, -3, 4, 10]

    # Concatenating the two arrays
    arr3 = arr1 + arr2

    # Sorting the resultant array
    arr3.sort()

    print("Median = ", Solution(arr3))

# This code is contributed by kush11
C#
// C# program for the above approach
using System;
using System.Collections.Generic;

public class GFG {
    public static int Solution(int[] arr)
    {
        int n = arr.Length;

        // If length of array is even
        if (n % 2 == 0) {
            int z = n / 2;
            int e = arr[z];
            int q = arr[z - 1];

            int ans = (e + q) / 2;
            return ans;
        }

        // If length if array is odd
        else {
            int z = n / 2;
            return arr[z];
        }
    }

    // Driver Code
    static public void Main()
    {

        // TODO Auto-generated method stub
        int[] arr1 = { -5, 3, 6, 12, 15 };
        int[] arr2 = { -12, -10, -6, -3, 4, 10 };

        // Merge two array into one array
        var myList = new List<int>();
        myList.AddRange(arr1);
        myList.AddRange(arr2);
        int[] arr3 = myList.ToArray();

        // Sort the merged array
        Array.Sort(arr3);

        // calling the method
        Console.Write("Median = " + Solution(arr3));
    }
}

// This code is contributed by Shubhamsingh10
Javascript
// Javascript program for the above approach

function Solution(arr, n)
{
 
    // If length of array is even
     if (n % 2 == 0) 
     {
       var z = n / 2;
       var e = arr[z];
       var q = arr[z - 1];
       var ans = (e + q) / 2;
       return ans;
     }
   
     // If length if array is odd
    else 
     {
       var z = Math.floor(n / 2);
       return arr[z];
     }
}

// Driver Code   
// TODO Auto-generated method stub
var arr1 = [ -5, 3, 6, 12, 15 ];
var arr2 = [ -12, -10, -6, -3, 4, 10 ];

var i =  arr1.length;
var j =  arr2.length;

var l =  i+j;
// Merge two array into one array
const arr3 = arr1.concat(arr2);

// Sort the merged array
arr3.sort(function(a, b) {
  return a - b;
});

// calling the method
console.log("Median = " + Solution(arr3, l));

// This code is contributed by Shubham Singh

Output
Median = 3

Time Complexity: O((N + M) * Log (N + M)), Time required to sort the array of size N + M
Auxiliary Space: O(N + M), Creating a new array of size N+M.

Median of two sorted arrays of different sizes by Merging Arrays efficiently:

The given arrays are sorted, so merge the sorted arrays in an efficient way and keep the count of elements inserted in the output array or printed form. So when the elements in the output array are half the original size of the given array print the element as a median element. There are two cases: 

  • Case 1: M+N is odd, the median is at (M+N)/2th index in the array obtained after merging both the arrays.
  • Case 2: M+N is even, the median will be the average of elements at index ((M+N)/2 – 1) and (M+N)/2 in the array obtained after merging both the arrays

Illustration:

Given two array ar1[ ]= { 900 } and ar2[ ] = { 5, 8, 10, 20 } , n => Size of ar1 = 1 and m => Size of ar2 = 4

  • Loop will run from 0 till 2. 
    • First iteration : { 900 }  { 5, 8, 10, 20 } , m1 = 5 
    • Second iteration : { 900 }  { 5, 8, 10, 20 }, m1 = 8
    • Third iteration : { 900 }  { 5, 8, 10, 20 }, m1 = 10
  • As size of ar1 + ar2 = odd , hence we return m1 = 10 as the median
 

Below is the implementation of the above approach:

C++
// A Simple Merge based O(n) solution to find
// median of two sorted arrays
#include <bits/stdc++.h>
using namespace std;

/* This function returns median of ar1[] and ar2[].
Assumption in this function:
Both ar1[] and ar2[] are sorted arrays */
int getMedian(int ar1[], int ar2[], int n, int m)
{
    int i = 0; /* Current index of input array ar1[] */
    int j = 0; /* Current index of input array ar2[] */
    int count;
    int m1 = -1, m2 = -1;
    /*loop till (m+n)/2*/
    for (count = 0; count <= (m + n) / 2; count++) {
        // store (n+m)/2-1 in m2
        m2 = m1;
        if (i != n && j != m) {
            m1 = (ar1[i] > ar2[j]) ? ar2[j++] : ar1[i++];
        }
        else if (i < n) {
            m1 = ar1[i++];
        }
        // for case when j<m,
        else {
            m1 = ar2[j++];
        }
    }
    // Since there are (n+m) elements,
    // There are following two cases
    // if n+m is odd then the middle
    // index is median i.e. (m+n)/2
    // other wise median will be average of elements
    // at index ((m+n)/2 - 1) and (m+n)/2
    // in the array obtained after merging ar1 and ar2
    if ((m + n) % 2 == 1) {
        return m1;
    }
    else {
        return (m1 + m2) / 2;
    }
}
/* Driver code */
int main()
{
    int ar1[] = { 900 };
    int ar2[] = { 5, 8, 10, 20 };
    int n1 = sizeof(ar1) / sizeof(ar1[0]);
    int n2 = sizeof(ar2) / sizeof(ar2[0]);
    cout << getMedian(ar1, ar2, n1, n2);
}

// This is code is contributed by rathbhupendra, modified by
// rajesh999
Java
import java.io.*;

class GFG {

    // Function to calculate median
    static int getMedian(int ar1[], int ar2[], int n, int m)
    {

        // Current index of input array ar1[]
        int i = 0;

        // Current index of input array ar2[]
        int j = 0;
        int count;
        int m1 = -1, m2 = -1;

        // Since there are (n+m) elements,
        // There are following two cases
        // if n+m is odd then the middle
        // index is median i.e. (m+n)/2
        if ((m + n) % 2 == 1) {
            for (count = 0; count <= (n + m) / 2; count++) {
                if (i != n && j != m) {
                    m1 = (ar1[i] > ar2[j]) ? ar2[j++]
                                           : ar1[i++];
                }
                else if (i < n) {
                    m1 = ar1[i++];
                }

                // for case when j<m,
                else {
                    m1 = ar2[j++];
                }
            }
            return m1;
        }

        // median will be average of elements
        // at index ((m+n)/2 - 1) and (m+n)/2
        // in the array obtained after merging
        // ar1 and ar2
        else {
            for (count = 0; count <= (n + m) / 2; count++) {
                m2 = m1;
                if (i != n && j != m) {
                    m1 = (ar1[i] > ar2[j]) ? ar2[j++]
                                           : ar1[i++];
                }
                else if (i < n) {
                    m1 = ar1[i++];
                }

                // for case when j<m,
                else {
                    m1 = ar2[j++];
                }
            }
            return (m1 + m2) / 2;
        }
    }

    // Driver code
    public static void main(String[] args)
    {
        int ar1[] = { 900 };
        int ar2[] = { 5, 8, 10, 20 };

        int n1 = ar1.length;
        int n2 = ar2.length;

        System.out.println(getMedian(ar1, ar2, n1, n2));
    }
}
Python3
# A Simple Merge based O(n) solution to find
# median of two sorted arrays

""" This function returns median of ar1[] and ar2[]. 
Assumption in this function: 
Both ar1[] and ar2[] are sorted arrays """

def getMedian(ar1, ar2, n, m):

    i = 0  # Current index of input array ar1[]
    j = 0  # Current index of input array ar2[]
    m1, m2 = -1, -1
    for count in range(((n + m) // 2) + 1):
        m2 = m1
        if(i != n and j != m):
            if ar1[i] > ar2[j]:
                m1 = ar2[j]
                j += 1
            else:
                m1 = ar1[i]
                i += 1
        elif(i < n):
            m1 = ar1[i]
            i += 1
            # for case when j<m,
        else:
            m1 = ar2[j]
            j += 1
           # return m1 if it's length odd else return (m1+m2)//2
    return m1 if (n + m) % 2 == 1 else (m1 + m2) // 2


# Driver code
ar1 = [900]
ar2 = [5, 8, 10, 20]

n1 = len(ar1)
n2 = len(ar2)
print(getMedian(ar1, ar2, n1, n2))

# This code is contributed by isandeep2183 (Sandeep Kumar Sharma)
C#
using System;

class GFG {

    // Function to calculate median
    static int getMedian(int[] ar1, int[] ar2, int n, int m)
    {

        // Current index of input array ar1[]
        int i = 0;

        // Current index of input array ar2[]
        int j = 0;

        int count;
        int m1 = -1, m2 = -1;

        // Since there are (n+m) elements,
        // There are following two cases
        // if n+m is odd then the middle
        // index is median i.e. (m+n)/2
        if ((m + n) % 2 == 1) {
            for (count = 0; count <= (n + m) / 2; count++) {
                if (i != n && j != m) {
                    m1 = (ar1[i] > ar2[j]) ? ar2[j++]
                                           : ar1[i++];
                }
                else if (i < n) {
                    m1 = ar1[i++];
                }

                // for case when j<m,
                else {
                    m1 = ar2[j++];
                }
            }
            return m1;
        }

        // median will be average of elements
        // at index ((m+n)/2 - 1) and (m+n)/2
        // in the array obtained after merging
        // ar1 and ar2
        else {
            for (count = 0; count <= (n + m) / 2; count++) {
                m2 = m1;
                if (i != n && j != m) {
                    m1 = (ar1[i] > ar2[j]) ? ar2[j++]
                                           : ar1[i++];
                }
                else if (i < n) {
                    m1 = ar1[i++];
                }

                // for case when j<m,
                else {
                    m1 = ar2[j++];
                }
            }
            return (m1 + m2) / 2;
        }
    }

    // Driver code
    public static void Main(String[] args)
    {
        int[] ar1 = { 900 };
        int[] ar2 = { 5, 8, 10, 20 };

        int n1 = ar1.Length;
        int n2 = ar2.Length;

        Console.WriteLine(getMedian(ar1, ar2, n1, n2));
    }
}
//This code is contributed by isandeep2183 ( Sandeep Kumar Sharma ) 
Javascript
// A Simple Merge based O(n) solution to find
// median of two sorted arrays

// This function returns median of ar1[] and ar2[].
// Assumption in this function:
// Both ar1[] and ar2[] are sorted arrays 
function getMedian(ar1, ar2, n, m)
{
    
    // Current index of input array ar1[] 
    let i = 0; 
    
    // Current index of input array ar2[] 
    let j = 0; 
    let count;
    let m1 = -1, m2 = -1;

    // Since there are (n+m) elements,
    // There are following two cases
    // if n+m is odd then the middle
    // index is median i.e. (m+n)/2
    if ((m + n) % 2 == 1)
    {
        for(count = 0; 
            count <= (n + m) / 2; 
            count++)
        {
            if (i != n && j != m)
            {
                m1 = (ar1[i] > ar2[j]) ? 
                    ar2[j++] : ar1[i++];
            }
            else if(i < n)
            {
                m1 = ar1[i++];
            }
            
            // For case when j<m,
            else
            {
                m1 = ar2[j++];
            }
        }
        return m1;
    }

    // Median will be average of elements
    // at index ((m+n)/2 - 1) and (m+n)/2
    // in the array obtained after merging
    // ar1 and ar2
    else
    {
        for(count = 0; 
            count <= (n + m) / 2; 
            count++)
        {
            m2 = m1;
            if (i != n && j != m)
            {
                m1 = (ar1[i] > ar2[j]) ? 
                    ar2[j++] : ar1[i++];
            }
            else if(i < n)
            {
                m1 = ar1[i++];
            }
            
            // For case when j<m,
            else
            {
                m1 = ar2[j++];
            }
        }
        return (m1 + m2) / 2;
    }
}
    
// Driver code
let ar1 = [900];
let ar2 = [5, 8, 10, 20];

let n1 = ar1.length;
let n2 = ar2.length;
console.log(getMedian(ar1, ar2, n1, n2));

// This code is contributed by isandeep(Sandeep Kumar Sharma)

Output
10

Time Complexity: O(M + N). To merge both arrays O(M+N) time is needed.
Auxiliary Space: O(1). No extra space is required.

Median of two sorted arrays of different sizes using Binary Search:

The given two arrays are sorted, so we can utilize the ability of Binary Search to divide the array and find the median. 

Median means the point at which the whole array is divided into two parts. Hence since the two arrays are not merged so to get the median we require merging which is costly. 

Hence instead of merging, we will use a modified binary search algorithm to efficiently find the median.

Below is the implementation:

C++
#include <bits/stdc++.h>
using namespace std;

// Method to find median
double Median(vector<int>& A, vector<int>& B)
{
    int n = A.size();
    int m = B.size();
    if (n > m)
        return Median(B, A); // Swapping to make A smaller

    int start = 0;
    int end = n;
    int realmidinmergedarray = (n + m + 1) / 2;

    while (start <= end) {
        int mid = (start + end) / 2;
        int leftAsize = mid;
        int leftBsize = realmidinmergedarray - mid;
        int leftA
            = (leftAsize > 0)
                  ? A[leftAsize - 1]
                  : INT_MIN; // checking overflow of indices
        int leftB
            = (leftBsize > 0) ? B[leftBsize - 1] : INT_MIN;
        int rightA
            = (leftAsize < n) ? A[leftAsize] : INT_MAX;
        int rightB
            = (leftBsize < m) ? B[leftBsize] : INT_MAX;

        // if correct partition is done
        if (leftA <= rightB and leftB <= rightA) {
            if ((m + n) % 2 == 0)
                return (max(leftA, leftB)
                        + min(rightA, rightB))
                       / 2.0;
            return max(leftA, leftB);
        }
        else if (leftA > rightB) {
            end = mid - 1;
        }
        else
            start = mid + 1;
    }
    return 0.0;
}

// Driver code
int main()
{
    vector<int> arr1 = { -5, 3, 6, 12, 15 };
    vector<int> arr2 = { -12, -10, -6, -3, 4, 10 };
    cout << "Median of the two arrays are" << endl;
    cout << Median(arr1, arr2);
    return 0;
}
Java
public class GFG {

    // Method to find median
    static double Median(int[] A, int[] B)
    {
        int n = A.length;
        int m = B.length;
        if (n > m)
            return Median(B,
                          A); // Swapping to make A smaller

        int start = 0;
        int end = n;
        int realmidinmergedarray = (n + m + 1) / 2;

        while (start <= end) {
            int mid = (start + end) / 2;
            int leftAsize = mid;
            int leftBsize = realmidinmergedarray - mid;
            int leftA
                = (leftAsize > 0)
                      ? A[leftAsize - 1]
                      : Integer
                            .MIN_VALUE; // checking overflow
                                        // of indices
            int leftB = (leftBsize > 0) ? B[leftBsize - 1]
                                        : Integer.MIN_VALUE;
            int rightA = (leftAsize < n)
                             ? A[leftAsize]
                             : Integer.MAX_VALUE;
            int rightB = (leftBsize < m)
                             ? B[leftBsize]
                             : Integer.MAX_VALUE;

            // if correct partition is done
            if (leftA <= rightB && leftB <= rightA) {
                if ((m + n) % 2 == 0)
                    return (Math.max(leftA, leftB)
                            + Math.min(rightA, rightB))
                        / 2.0;
                return Math.max(leftA, leftB);
            }
            else if (leftA > rightB) {
                end = mid - 1;
            }
            else
                start = mid + 1;
        }
        return 0.0;
    }

    // Driver code
    public static void main(String[] args)
    {
        int[] arr1 = { -5, 3, 6, 12, 15 };
        int[] arr2 = { -12, -10, -6, -3, 4, 10 };
        System.out.println("Median of the two arrays are");
        System.out.println(Median(arr1, arr2));
    }
}

// This code is contributed by Hritik
Python3
class Solution:

    # Method to find median
    def Median(self, A, B):

          # Assumption both A and B cannot be empty
        n = len(A)
        m = len(B)
        if (n > m):
            return self.Median(B, A)  # Swapping to make A smaller

        start = 0
        end = n
        realmidinmergedarray = (n + m + 1) // 2

        while (start <= end):
            mid = (start + end) // 2
            leftAsize = mid
            leftBsize = realmidinmergedarray - mid

            # checking overflow of indices
            leftA = A[leftAsize - 1] if (leftAsize > 0) else float('-inf')
            leftB = B[leftBsize - 1] if (leftBsize > 0) else float('-inf')
            rightA = A[leftAsize] if (leftAsize < n) else float('inf')
            rightB = B[leftBsize] if (leftBsize < m) else float('inf')

            # if correct partition is done
            if leftA <= rightB and leftB <= rightA:
                if ((m + n) % 2 == 0):
                    return (max(leftA, leftB) + min(rightA, rightB)) / 2.0
                return max(leftA, leftB)

            elif (leftA > rightB):
                end = mid - 1
            else:
                start = mid + 1


# Driver code
ans = Solution()
arr1 = [-5, 3, 6, 12, 15]
arr2 = [-12, -10, -6, -3, 4, 10]
print("Median of the two arrays is")
print(ans.Median(arr1, arr2))

# This code is contributed by Arpan
C#
using System;

public class GFG {

    // Method to find median
    static double Median(int[] A, int[] B)
    {
        int n = A.Length;
        int m = B.Length;
        if (n > m)
            return Median(B,
                          A); // Swapping to make A smaller

        int start = 0;
        int end = n;
        int realmidinmergedarray = (n + m + 1) / 2;

        while (start <= end) {
            int mid = (start + end) / 2;
            int leftAsize = mid;
            int leftBsize = realmidinmergedarray - mid;
            int leftA
                = (leftAsize > 0)
                      ? A[leftAsize - 1]
                      : Int32.MinValue; // checking overflow
                                        // of indices
            int leftB = (leftBsize > 0) ? B[leftBsize - 1]
                                        : Int32.MinValue;
            int rightA = (leftAsize < n) ? A[leftAsize]
                                         : Int32.MaxValue;
            int rightB = (leftBsize < m) ? B[leftBsize]
                                         : Int32.MaxValue;

            // if correct partition is done
            if (leftA <= rightB && leftB <= rightA) {
                if ((m + n) % 2 == 0)
                    return (Math.Max(leftA, leftB)
                            + Math.Min(rightA, rightB))
                        / 2.0;
                return Math.Max(leftA, leftB);
            }
            else if (leftA > rightB) {
                end = mid - 1;
            }
            else
                start = mid + 1;
        }
        return 0.0;
    }

    // Driver code
    public static void Main()
    {
        int[] arr1 = { -5, 3, 6, 12, 15 };
        int[] arr2 = { -12, -10, -6, -3, 4, 10 };
        Console.WriteLine("Median of the two arrays are");
        Console.WriteLine(Median(arr1, arr2));
    }
}

// This code is contributed by Shubham Singh
Javascript
<script>
        // JavaScript Program to implement
        // the above approach

        // Method to find median
        function Median(A, B) {
            let n = A.length;
            let m = B.length;
            if (n > m)
                return Median(B, A); // Swapping to make A smaller

            let start = 0;
            let end = n;
            let realmidinmergedarray = Math.floor((n + m + 1) / 2);

            while (start <= end) {
                let mid = Math.floor((start + end) / 2);
                let leftAsize = mid;
                let leftBsize = realmidinmergedarray - mid;
                let leftA
                    = (leftAsize > 0)
                        ? A[leftAsize - 1]
                        : Number.MIN_VALUE; // checking overflow of indices
                let leftB
                    = (leftBsize > 0) ? B[leftBsize - 1] : INT_MIN;
                let rightA
                    = (leftAsize < n) ? A[leftAsize] : INT_MAX;
                let rightB
                    = (leftBsize < m) ? B[leftBsize] : INT_MAX;

                // if correct partition is done
                if (leftA <= rightB && leftB <= rightA) {
                    if ((m + n) % 2 == 0)
                        return Math.floor((Math.max(leftA, leftB)
                            + Math.min(rightA, rightB))
                            / 2.0);
                    return Math.max(leftA, leftB);
                }
                else if (leftA > rightB) {
                    end = mid - 1;
                }
                else
                    start = mid + 1;
            }
            return 0.0;
        }

        // Driver code
        let arr1 = [-5, 3, 6, 12, 15];
        let arr2 = [-12, -10, -6, -3, 4, 10];
        document.write("Median of the two arrays are" + "<br>");
        document.write(Median(arr1, arr2))

// This code is contributed by Potta Lokesh
    </script>

Output
Median of the two arrays are
3

Time Complexity: O(min(log M, log N)): Since binary search is being applied on the smaller of the 2 arrays
Auxiliary Space: O(1)

Median of two sorted arrays of different sizes using Priority Queue: 

In this Approach we have used Priority Queue (min Heap) to find out the median. 

The Idea is simple, just push the elements into a single Priority Queue from both arrays. Now we have to find median from priority queue by performing a simple traversal through it upto median.

Illustration:

A[ ] = {-2, 3, 4, 5}, N = 4 & B[ ] = {-4, -1, 7, 8, 9}, M = 5

Step 1: Adding elements to priority queue(pq) from array

  • pq.push(-2)
  • pq.push(3)
  • pq.push(4)
  • pq.push(5)

After adding array A elements to priority queue it will look as pq = {-2, 3, 4, 5}

Step 2: Adding elements to priority queue(pq) from array B

  • pq.push(-4)
  • pq.push(-1)
  • pq.push(7)
  • pq.push(8)
  • pq.push(9)

After adding array B elements to priority queue it will look as pq = {-4, -2, -1, 3, 4, 5, 7, 8, 9}

Step 3: Now we have to find median from Priority Queue based on following conditions: 

  • if N+M is odd 
    • then traverse priority queue upto (n+m)/2 by popping element by element
    • Then display median as pq.top()
  • if N+M is even 
    • then traverse priority queue upto  (n+m)/2 && ((n+m)/2)-1
    • Then median = average of both top values of priority queue

In this case the median is 4

Below is the implementation of the above problem:

C++
#include <bits/stdc++.h>
using namespace std;

// Method to find median
double Median(vector<int>& A, vector<int>& B)
{
    int i;
    int n = A.size();
    int m = B.size();
    // initializing Priority Queue (Min Heap)
    priority_queue<int, vector<int>, greater<int> > pq;
    // pushing array A values to priority Queue
    for (i = 0; i < n; i++)
        pq.push(A[i]);
    // pushing array B values to priority Queue
    for (i = 0; i < m; i++)
        pq.push(B[i]);
    int check = n + m;
    double count = -1;
    double mid1, mid2;
    while (!pq.empty()) {
        count++;
        // returning mid value if combined length(n+m) is
        // odd
        if (check % 2 != 0 && count == check / 2) {
            double ans = pq.top();
            return ans;
        }
        // maintaining mid1 value if combined length(n+m) is
        // even where we need to maintain both mid values in
        // case of even combined length
        if (check % 2 == 0 && count == (check / 2) - 1)
            mid1 = pq.top();
        // now returning the mid2 value with previous
        // maintained mid1 value by 2
        if (check % 2 == 0 && count == check / 2) {
            mid2 = pq.top();
            double ans = (mid1 + mid2) / 2;
            return ans;
        }
        pq.pop();
    }
    return 0.00000;
}

// Driver code
int main()
{
    vector<int> arr1 = { -2, 3, 4, 5 };
    vector<int> arr2 = { -4, -1, 7, 8, 9 };
    cout << "Median of the two arrays are" << endl;
    cout << Median(arr1, arr2);
    return 0;
}
Java
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Vector;

public class Main {

    // Method to find median
    public static double Median(Vector<Integer> A,
                                Vector<Integer> B)
    {
        int i;
        int n = A.size();
        int m = B.size();
        // initializing Priority Queue (Min Heap)
        PriorityQueue<Integer> pq
            = new PriorityQueue<Integer>();
        // pushing array A values to priority Queue
        for (i = 0; i < n; i++) {
            pq.add(A.get(i));
        }
        // pushing array B values to priority Queue
        for (i = 0; i < m; i++) {
            pq.add(B.get(i));
        }
        int check = n + m;
        double count = -1;
        double mid1 = -1, mid2 = -1;
        while (!pq.isEmpty()) {
            count++;
            // returning mid value if combined length(n+m)
            // is odd
            if (check % 2 != 0 && count == check / 2) {
                double ans = pq.peek();
                return ans;
            }
            // maintaining mid1 value if combined
            // length(n+m) is even where we need to maintain
            // both mid values in case of even combined
            // length
            if (check % 2 == 0
                && count == (check / 2) - 1) {
                mid1 = pq.peek();
            }
            // now returning the mid2 value with previous
            // maintained mid1 value by 2
            if (check % 2 == 0 && count == check / 2) {
                mid2 = pq.peek();
                double ans = (mid1 + mid2) / 2;
                return ans;
            }
            pq.poll();
        }
        return 0.00000;
    }

    // Driver code
    public static void main(String[] args)
    {
        Vector<Integer> arr1 = new Vector<Integer>();
        arr1.add(-2);
        arr1.add(3);
        arr1.add(4);
        arr1.add(5);

        Vector<Integer> arr2 = new Vector<Integer>();
        arr2.add(-4);
        arr2.add(-1);
        arr2.add(7);
        arr2.add(8);
        arr2.add(9);

        System.out.println("Median of the two arrays are");
        System.out.println(Median(arr1, arr2));
    }
}
Python3
# Python code for the above approach

import heapq


def Median(A, B):
    n, m = len(A), len(B)
    # initializing Priority Queue (Min Heap)
    pq = []
    # pushing array A values to priority Queue
    for i in range(n):
        heapq.heappush(pq, A[i])
    # pushing array B values to priority Queue
    for i in range(m):
        heapq.heappush(pq, B[i])
    check = n + m
    count = -1
    mid1, mid2 = -1, -1
    while pq:
        count += 1
        # returning mid value if combined length(n+m) is odd
        if check % 2 != 0 and count == check // 2:
            return pq[0]
        # maintaining mid1 value if combined length(n+m) is even
        # where we need to maintain both mid values in case of
        # even combined length
        if check % 2 == 0 and count == (check // 2) - 1:
            mid1 = pq[0]
        # now returning the mid2 value with previous maintained
        # mid1 value by 2
        if check % 2 == 0 and count == check // 2:
            mid2 = heapq.heappop(pq)
            return (mid1 + mid2) / 2
        heapq.heappop(pq)
    return 0.00000


# Driver code
arr1 = [-2, 3, 4, 5]
arr2 = [-4, -1, 7, 8, 9]

print("Median of the two arrays are")
print(Median(arr1, arr2))

# This code is contributed by karthik
C#
using System;
using System.Collections.Generic;

namespace MedianOfTwoSortedArrays {
class Program {
    static double Median(List<int> A, List<int> B)
    {
        int n = A.Count;
        int m = B.Count;
        int i;
        // initializing Priority Queue (Min Heap)
        var pq = new SortedSet<int>();
        // pushing array A values to priority Queue
        for (i = 0; i < n; i++)
            pq.Add(A[i]);
        // pushing array B values to priority Queue
        for (i = 0; i < m; i++)
            pq.Add(B[i]);
        int check = n + m;
        double count = -1;
        double mid1, mid2;
        while (pq.Count != 0) {
            count++;
            // returning mid value if combined length(n+m)
            // is odd
            if (check % 2 != 0 && count == check / 2) {
                double ans = pq.Min;
                return ans;
            }
            // maintaining mid1 value if combined
            // length(n+m) is even where we need to maintain
            // both mid values in case of even combined
            // length
            if (check % 2 == 0
                && count == (check / 2) - 1) {
                mid1 = pq.Min;
                // now returning the mid2 value with
                // previous maintained mid1 value by 2
                if (check % 2 == 0 && count == check / 2) {
                    mid2 = pq.Min;
                    double ans = (mid1 + mid2) / 2;
                    return ans;
                }
            }
            pq.Remove(pq.Min);
        }
        return 0.00000;
    }
    // Driver Code
    static void Main(string[] args)
    {
        List<int> arr1 = new List<int>{ -2, 3, 4, 5 };
        List<int> arr2 = new List<int>{ -4, -1, 7, 8, 9 };
        Console.WriteLine("Median of the two arrays are");
        Console.WriteLine(Median(arr1, arr2));
        Console.ReadLine();
    }
}
}
Javascript
// Method to find median
function Median(A, B) {
    let n = A.length;
    let m = B.length;
    //initializing Priority Queue (Min Heap)
    let pq = new PriorityQueue();
    //pushing array A values to priority Queue
    for (let i = 0; i < n; i++) {
        pq.push(A[i]);
    }
    //pushing array B values to priority Queue
    for (let i = 0; i < m; i++) {
        pq.push(B[i]);
    }
    let check = n + m;
    let count = -1;
    let mid1, mid2;
    while (!pq.isEmpty()) {
        count++;
        //returning mid value if combined length(n+m) is odd
        if (check % 2 !== 0 && count === Math.floor(check / 2)) {
            let ans = pq.top();
            return ans;
        }
        //maintaining mid1 value if combined length(n+m) is even
        //where we need to maintain both mid values in case of even combined length
        if (check % 2 === 0 && count === (check / 2) - 1) {
            mid1 = pq.top();
        }
        //now returning the mid2 value with previous maintained mid1 value by 2
        if (check % 2 === 0 && count === check / 2) {
            mid2 = pq.top();
            let ans = (mid1 + mid2) / 2;
            return ans;
        }
        pq.pop();
    }
    return 0.00000;
}

// Priority Queue (Min Heap) implementation
class PriorityQueue {
    constructor() {
        this.data = [];
    }
    push(value) {
        this.data.push(value);
        this.bubbleUp(this.data.length - 1);
    }
    pop() {
        let result = this.data[0];
        let end = this.data.pop();
        if (this.data.length > 0) {
            this.data[0] = end;
            this.bubbleDown(0);
        }
        return result;
    }
    top() {
        return this.data[0];
    }
    isEmpty() {
        return this.data.length === 0;
    }
    bubbleUp(index) {
        let parent = Math.floor((index + 1) / 2) - 1;
        if (parent >= 0 && this.data[parent] > this.data[index]) {
            [this.data[parent], this.data[index]] = [this.data[index], this.data[parent]];
            this.bubbleUp(parent);
        }
    }
    bubbleDown(index) {
        let child1 = (index + 1) * 2 - 1;
        let child2 = (index + 1) * 2;
        let minIndex = index;
        if (child1 < this.data.length && this.data[child1] < this.data[minIndex]) {
            minIndex = child1;
        }
        if (child2 < this.data.length && this.data[child2] < this.data[minIndex]) {
            minIndex = child2;
        }
        if (minIndex !== index) {
            [this.data[index], this.data[minIndex]] = [this.data[minIndex], this.data[index]];
            this.bubbleDown(minIndex);
        }
    }
}

// Driver code
let arr1 = [-2, 3, 4, 5];
let arr2 = [-4, -1, 7, 8, 9];
console.log("Median of the two arrays are");
console.log(Median(arr1, arr2));

Output
Median of the two arrays are
4

Time Complexity: O((n + m) log(n + m)), Since the priority queue is implemented from two arrays
Auxiliary Space: O(N+M): for storing two array values in the priority queue.



Previous Article
Next Article

Similar Reads

Median of two sorted arrays of different sizes | Set 1 (Linear)
This is an extension of the median of two sorted arrays of equal size problem. Here we handle arrays of unequal size also. Examples: Input: a[] = {1, 12, 15, 26, 38} b[] = {2, 13, 24} Output: 14 Explanation: After merging arrays the result is 1, 2, 12, 13, 15, 24, 26, 38 median = (13 + 15)/2 = 14. Input: a[] = {1, 3, 5, 7} b[] = {2, 4, 6, 8} Output
12 min read
Median of two Sorted Arrays of Different Sizes using Binary Search
Given two sorted arrays, a[] and b[] os size n and m, the task is to find the median of these sorted arrays, in O(log(min(n, m)), when n is the number of elements in the first array, and m is the number of elements in the second array. Note: In case of even numbers in total and if we want to return a median that exists in the merged array we can re
15+ min read
Merge K sorted arrays of different sizes | ( Divide and Conquer Approach )
Given k sorted arrays of different length, merge them into a single array such that the merged array is also sorted.Examples: Input : {{3, 13}, {8, 10, 11} {9, 15}} Output : {3, 8, 9, 10, 11, 13, 15} Input : {{1, 5}, {2, 3, 4}} Output : {1, 2, 3, 4, 5} Let S be the total number of elements in all the arrays.Simple Approach: A simple approach is to
8 min read
Generate all possible sorted arrays from alternate elements of two given sorted arrays
Given two sorted arrays A and B, generate all possible arrays such that the first element is taken from A then from B then from A, and so on in increasing order till the arrays are exhausted. The generated arrays should end with an element from B. Example: A = {10, 15, 25} B = {1, 5, 20, 30} The resulting arrays are: 10 20 10 20 25 30 10 30 15 20 1
12 min read
Median of two sorted arrays of same size
There are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n)) Recommended ProblemSum of Middle Elements of two sorted arrays Solve Problem Note: Since the size of the set for which we are looking for the medi
15+ min read
Merge k sorted arrays | Set 2 (Different Sized Arrays)
Given k sorted arrays of possibly different sizes, merge them and print the sorted output.Examples: Input: k = 3 arr[][] = { {1, 3}, {2, 4, 6}, {0, 9, 10, 11}} ;Output: 0 1 2 3 4 6 9 10 11 Input: k = 2 arr[][] = { {1, 3, 20}, {2, 4, 6}} ;Output: 1 2 3 4 6 20 We have discussed a solution that works for all arrays of the same size in Merge k sorted a
7 min read
Find Median for each Array element by excluding the index at which Median is calculated
Given an array A[] of N integers where N is even, . the task is to generate an array of medians where the median of the array is calculated by taking the median of array A[] excluding A[i]-th element. Examples: Input N = 4, A = [2, 4, 4, 3]Output: [4, 3, 3, 4]Explanation: Median after removing A[0]: New sorted array will be [3, 4, 4]. Median = 4. M
10 min read
Check if two sorted arrays can be merged to form a sorted array with no adjacent pair from the same array
Given two sorted arrays A[] and B[] of size N, the task is to check if it is possible to merge two given sorted arrays into a new sorted array such that no two consecutive elements are from the same array. Examples: Input: A[] = {3, 5, 8}, B[] = {2, 4, 6}Output: Yes Explanation: Merged array = {B[0], A[0], B[1], A[1], B[2], A[2]} Since the resultan
15+ min read
Maximum OR sum of sub-arrays of two different arrays
Given two arrays of positive integers. Select two sub-arrays of equal size from each array and calculate maximum possible OR sum of the two sub-arrays. Note: Let f(x, l, r) is the OR sum of all the elements in the range [l, r] in array x. Examples : Input : A[] = {1, 2, 4, 3, 2} B[] = {2, 3, 3, 12, 1} Output : 22 Explanation: Here, one way to get m
5 min read
Maximize sum of max and min of each of K Arrays obtained by dividing given Array into given sizes
Given two arrays, arr[] of N size and div[] of size K. Divide arr[] into K different arrays, each of div[i] size. The task is to find the total sum after maximizing the sum of maximum and minimum of each divided array. Examples: Input: arr[] = {3, 1, 7, 4}, div[] = {1, 3}, N = 4, K = 2Output: 19Explanation: Divide the array in the following way: {7
9 min read
three90RightbarBannerImg