Median of two sorted arrays
You are given two sorted arrays 'A' & 'B' of sizes 'N' & 'M'. You need to find the median of the two arrays when merged. If the total number of elements i.e., N + M is even then the median will be the mean of two medians.

Example:

Let array A = { 2, 4, 6, 8 } and array B = { 1, 3, 5, 7 }. The array after merging A and B will be { 1, 2, 3, 4, 5, 6, 7, 8 }. Here two medians are 4 & 5. So the median will be a mean of 4 & 5, which is 4.5.

Follow Up

Can you solve this in O(min(log N, log M)) time complexity?

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases. The first line of each test case contains two space-separated integers ‘N’ and ‘M’ representing the sizes of the two arrays. The second line of each test case contains 'N' space-separated integers representing the elements of the first array. The third line of each test case contains 'M' space-separated integers representing the elements of the second array.

Output format :

For each test case, print a single line containing a single integer denoting the median of the combined array. The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Median of two sorted arrays

You are given two sorted arrays 'A' & 'B' of sizes 'N' & 'M'. You need to find the median of the two arrays when merged. If the total number of elements i.e., N + M is even then the median will be the mean of two medians.

Example:

Let array A = { 2, 4, 6, 8 } and array B = { 1, 3, 5, 7 }. 
The array after merging A and B will be { 1, 2, 3, 4, 5, 6, 7, 8 }.
Here two medians are 4 & 5. So the median will be a mean of 4 & 5, which is 4.5.

Follow Up

Can you solve this in O(min(log N, log M)) time complexity?

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’ representing the sizes of the two arrays.

The second line of each test case contains 'N' space-separated integers representing the elements of the first array.

The third line of each test case contains 'M' space-separated integers representing the elements of the second array.

Output format :

For each test case, print a single line containing a single integer denoting the median of the combined array.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10 ^ 6
1 <= M <= 10 ^ 6
1 <= A[i] <= 10 ^ 9
1 <= B[i] <= 10 ^ 9

Time limit: 1 sec.

Accepted Answer

Step 1 : Tried out a few test cases on my own and checked for the output.
Step 2 : Using the linear approach, merged the sorted arrays by iterating over both of them and finding the mid point of the sorted and merged array.
Note: The time complexity for this solution was O(m+n) This wasn't the most optimised solution, a better solution can be given which solves the question in O(log m+log n)

Accepted Answer

Sorting

The first approach is by joining the array and again sorting is to get median.

The algorithm is as follows:

Create a new array of size of total number of elements.
Insert elements of both the arrays in the array.
Sort the array and find the median.

Space Complexity: OtherExplanation:

O(N + M) per test case, where ‘N’ and ‘M’ are the sizes of the arrays.

In the worst case, we will be creating a single array to insert all numbers.

Time Complexity: OtherExplanation:

O((N + M) * log(N + M)) per test case where ‘N’ & ‘M’ are the sizes of the two arrays.

In the worst case, we will be sorting the joined array.

Accepted Answer

Two pointer

The second approach is using a two-pointer approach to get middle elements.

The algorithm is as follows:

Initialize two pointers i and j to 0.
Move a pointer forward which has a smaller value.
Move the pointers until we process half the number of elements.
Then calculate the median.

Space Complexity: O(1)Explanation:

O(1).

In the worst case, we will be using constant space.

Time Complexity: OtherExplanation:

O(N + M), where ‘N’ & ‘M’ are the sizes of the two arrays.

In the worst case, we will be moving pointers (N + M) / 2 times.

Accepted Answer

Binary Search

The third approach is using binary search to find median.

The algorithm is as follows:

Use Binary Search to partition the smaller array in two parts.
Find the partition of the second array such that the sum of elements on the left side of the partition in both the arrays has half of the total elements.
Check if this partition is valid by verifying if the largest number of left partitions is smaller than the smallest number of the right partitions.
If the partition is valid then calculate and return the median.

Space Complexity: O(1)Explanation:

O(1).

In the worst case, we will be using constant space.

Time Complexity: OtherExplanation:

O(min(log N, log M)) per test case where ‘N’ & ‘M’ are the sizes of the two arrays.

In the worst case, we will be using a binary search on the smaller array.

You are given two sorted arrays 'A' & 'B' of sizes 'N' & 'M'. You need to find the median of the two arrays when merged. If the total number of elements i.e., N + M is even then the median will be the mean of two medians.

Example:

Follow Up

Input format:

Output format :

Note:

Constraints:

Top LinkedIn Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern