Median of Two Sorted Arrays

Median of Two Sorted Arrays of Same Size

Before getting into the problem statement of finding the median of two sorted arrays, let us first get a brief introduction about the arrays.

An array is a linear collection of values stored at contiguous memory locations. Array stores homogeneous values(similar data type values).

To learn more about the arrays, refer to the article - Arrays in Data Structure.

Note: A list is used to store one or more objects or data elements. Lists are used in python and java mostly. We can say that lists are similar to arrays.

Median is the mid element (middle element) of an sorted array if the number of elements in the array is odd. If the number of elements in the array is even then the median is the average of the two middle elements.

Problem Statement

We are provided with two sorted arrays named array_1 and array_2 of size n each and we need to find the median of the array obtained after merging the provided two sorted arrays.

The first input is the sequential set of elements of the first array.
The second input is the sequential set of elements of the second array.

Constraints

$array_1.length == m$
$array_2.length == n$
$0 <= m <= 1000$
$0 <= n <= 1000$
$1 <= m + n <= 2000$
$-10^6 <= array_1[i], array_2[i] <= 10^6$

Here, $m == n$ as both the arrays are of same length.

In some problems, you may find the number of test cases represented by t. So, we only need to call the findMedian function t-times.

The problem is to find the median of two sorted arrays.

Example

Let us look at some of the examples provided to find the median of two sorted arrays of same length.

Example 1: Given, first input array is [ 1, 12, 15, 26, 38 ] Given, second input array is [ 2, 13, 17, 30, 45 ]

Output:

Example 2: Given, first input the array is [ 1, 2 ] Given, second input array is [ 3, 4 ]

Output:

Explanation

Let us take the first example and find the median of two sorted arrays.

The first array (a1) is [ 1, 12, 15, 26, 38 ] The second array (a2) is [ 2, 13, 17, 30, 45 ]

After merging these two arrays, the merged array is [ 1, 2, 12, 13, 15, 17, 26, 30, 38, 45 ]

The average of the two middle elements is: $(15 + 17)/2$ i.e. 16.

Note: The size of the first array is n then the size of the merged array is 2n and hence we need to take the average of the two middle elements.

Approach 1: Simply Count While Merging

The most basic approach to finding the median of two sorted arrays can be counting the first n sorted elements of the merged array.

We can simply merge the two sorted arrays (just like the merge procedure of the Merge Sort algorithm). We also need to maintain a counter while traversing and comparing the two arrays.

Since there can be 2n elements in the array, whenever our counter reaches n, it means we have reached the median of the two arrays. We just need to take the average of the n th element and n+1th element as the size of the merged array is even.

Algorithm

The pseudo-code for the algorithm can be:

Implementation:

C++ code:

Java code:

Python code:

Output:

Complexity Analysis

In this basic approach to finding the median of two sorted arrays of the same length, we have traversed the arrays and counted the first n sorted elements of the merged array.

Time Complexity

As we are traversing only the first n elements of the arrays, the time complexity is O(n).

Space Complexity

We are not using any extra space rather than a count variable. So, space complexity is O(1).

Approach 2: By Comparing the Medians of Two Arrays

In the approach of finding the medians of two sorted arrays, we will find the medians of both the arrays and then compare them. Let us see the pseudo-code for the same for better understanding.

Algorithm

The pseudo-code for the algorithm can be:

Implementation

C++ code:

Java code:

Python code:

Output:

Complexity Analysis

In this approach of finding the median of two sorted arrays of the same length, we are first finding the median of each array and then finding the required median by dividing the array into sub-arrays.

Time Complexity

So, the time complexity is O(log n).

Space Complexity

We are not using any extra space. So, space complexity is O(1).

Approach 3: By Taking Union w/o Extra Space

In the approach of finding the medians of two sorted arrays, we will first find the union of both the arrays and then sort them. Let us see the pseudo-code for the same for better understanding.

Algorithm

The pseudo-code for the algorithm can be:

Implementation

C++ code:

Java code:

Python code:

Output:

Complexity Analysis

In this approach of finding the median of two sorted arrays of the same length, we are first finding the union of the two arrays, and then sorting both the arrays for a further operation.

Time Complexity

So, the time complexity is O(n log n).

Space Complexity

We are not using any extra space. So, space complexity is O(1).

Median of Two Sorted Arrays of Different Sizes

So far we have seen the approaches of finding the median of two sorted arrays of the same length.

Let us now discuss a variance of this problem where the size of both the arrays is not the same.

Problem Statement

We are provided with two sorted arrays (array_1 and array_2) of different lengths (n and m respectively) and we need to find the median of two sorted arrays obtained after merging the provided two sorted arrays.

The first input is the sequential set of elements of the first array.
The second input is the sequential set of elements of the second array.

Constraints

$array_1.length == m$
$array_2.length == n$
$0 <= m <= 1000$
$0 <= n <= 1000$
$1 <= m + n <= 2000$
$-10^6 <= array_1[i], array_2[i] <= 10^6$

In some problems, you may find the number of test cases represented by t. So, we only need to call the findMedian function t-times.

The problem is to find the median of two sorted arrays of different lengths.

Example

Let us look at some of the examples provided to find the second largest element in the array.

Example 1: Given first input array is [ -5, 3, 6, 12, 15 ] Given second input array is [ -12, -10, -6, -3, 4, 10 ] Output:

Example 2: Given the first input, array is [ 2, 3, 5, 8 ] Given second input array is [ 10, 12, 14, 16, 18, 20 ]

Output:

Example Explanation

Let us take the first example and find the median of two sorted arrays.

The first array (a1) is [ -5, 3, 6, 12, 15 ] The second array (a2) is [ -12, -10, -6, -3, 4, 10 ]

After merging these two arrays, the merged array is [ -12, -10, -6, -5, -3, 3, 4, 6, 10, 12, 15 ]

The median of the array is 3 as the size of the merged array is 11 so the median is present at the 5th index i.e. 11/2 (floor value comes out to be 5).

Approach 1: Linear and Simpler Approach

The most basic approach to finding the median of two sorted arrays can be counting the first n sorted elements of the merged array.

We can simply merge the two sorted arrays (just like the merge procedure of the Merge Sort algorithm). We also need to maintain a counter while traversing and comparing the two arrays.

The size of the merged array can be even or odd. Let us see both the cases:

If the size of the array is odd (i.e. $m + n$ is odd) then median is obtained as $(m + n) / 2$ .
If the size of the array is even (i.e. m + n is even) then the median is obtained as the average of $(m + n)/2 - 1$ and $(m + n)/2$ .

Algorithm

The pseudo-code for the algorithm can be:

Implementation

C++ code:

Java code:

Python code:

Output:

Complexity Analysis

In this basic approach to finding the median of two sorted arrays of different lengths, we have traversed the arrays and counted the first m + n sorted elements of the merged array.

Time Complexity

As we are traversing only the first m + n elements of the arrays, the time complexity is O(m + n).

Space Complexity

We are not using any extra space. So, space complexity is O(1).

Approach 2: Efficient Solution

An efficient approach of finding the median of two sorted arrays of varying sizes can be finding the median of both the arrays and then discarding the one half (sub-array) of both the arrays. Let us see the algorithm and code for a better understanding.

Algorithm

The pseudo-code for the algorithm can be:

Implementation

C++ code:

Java code:

Python code:

Output:

Complexity Analysis

In this approach to finding the median of two sorted arrays of different lengths, we have used the divide and conquer technique as in each step, we are discarding one-half of the array.

Time Complexity

So, the time complexity is O(min(log m, log n)).

Space Complexity

We are not using any extra space. So, space complexity is O(1).

Approach 3: Simple Mathematical Approach

In this approach of finding the median of two sorted arrays can be merging the two arrays into a single array and then sorting the resulting array. Now depending upon the size of the resultant array, we can easily find the median and return it.

Algorithm

The pseudo-code for the algorithm can be:

Implementation

C++ code:

Java code:

Python code:

Output:

Complexity Analysis

In this approach of finding the median of two sorted arrays of different lengths, we have merged both the input arrays into a merged array, we are then finding the mid element of the merged array according to the size of the array.

Time Complexity

So, the time complexity is O((n+m) log (n+m)).

Space Complexity

We are using a merged array as extra space. So, space complexity is O(n + m).

Approach 4: Binary Search

Another efficient approach to finding the median of two sorted arrays can be applying binary search and dividing the arrays into halves and finding the required median.

In this approach, we are not merging the array and performing a binary search but we are using the algorithm specified below.

Let us assume that we are provided two input arrays of varying lengths A, and B. (Here, the first array i.e. A is smaller in size). The size of the array A is n and the size of array B is m.

For example, array A = [ 1, 4, 7 ] and array B = [ 2, 3, 5, 6 ]

Let us see the algorithm using the above example.

We can say that the sum of the left part of both array A and array B will result in the left part of the resultant merged array.

Similarly, the sum of the right part of both array A and array B will result in the right part of the resultant merged array.

The merged array will be [ 1, 2, 3, 4, 5, 6, 7 ]

In this example, our median is 4. So, we can easily discard the right half of the combined array. Hence, in this approach, we will try to discard the part of the array that will not contain our answer.

Algorithm

The pseudo-code for the algorithm can be:

Implementation

C++ code:

Java code:

Python code:

Output:

Complexity Analysis

In this approach to finding the median of two sorted arrays of different lengths, we have performed a binary search on the array.

Time Complexity

So, the time complexity is O(min(log m, log n)).

Space Complexity

We are not using any extra space. So, space complexity is O(1).

Conclusion

The most basic approach to finding the median of two sorted arrays of the same length can be counting the first n sorted elements of the merged array. In this approach, the time complexity is O(n) and space complexity is O(1).
Another approach to finding the medians of two sorted arrays of the same length, can be finding the medians of both the arrays and then comparing them. In this approach, the time complexity is O(log n) and space complexity is O(1).
Another approach to finding the medians of two sorted arrays of the same length first can be finding the union of both the arrays and then sorting them respectively. In this approach, the time complexity is O(n log n) and space complexity is O(1).
The basic approach to finding the median of two sorted arrays of different lengths can be counting the first n sorted elements of the merged array. In this approach, the time complexity is O(m + n) and space complexity is O(1).
Another approach to finding the median of two sorted arrays of different lengths can be finding the median of both the arrays and then discarding the one half (sub-array) of both the arrays. In this approach, the time complexity is O(min(log m, log n) and space complexity is O(1).
Another approach to finding the median of two sorted arrays of different lengths can be merging the two arrays into a single array and then sorting it. Now, we can easily find the median and return it. In this approach, the time complexity is O((n+m) log (n+m)) and space complexity is O(n + m).
Another approach to finding the median of two sorted arrays of different lengths can be applying binary search and diving the arrays into halves and finding the required median. In this approach, the time complexity is O(min(log m, log n)) and space complexity is O(1).