About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Median of Two Sorted Arrays Problem

Problem Statement

There are 2 sorted arrays arr and brr of size n and m respectively. Write an algorithm to find the median of the array obtained after merging arrays arr and brr (i.e. array of length n + m). 

1) Desired complexity is logarithmic and not linear.

2) We define median as following:

==> For an array of odd length, the median is the middle element.

Example: arr = [4, 5, 6, 7], brr = [7, 8, 9]

-> After merging: arr + brr = [4, 5, 6, 7, 7, 8, 9]

The middle element is 7.

Median is 7.

==> For an array of even length, the median is the smaller number of the 2 middle elements.

Example: arr = [4, 5, 6], brr = [7, 8, 9]

-> After merging: arr + brr = [4, 5, 6, 7, 8, 9]

The 2 middle elements are 6 and 7.

Median is Min(6, 7) = 6.

Example

Input:

For custom input:

2

1

2

2

1

4

For the function:

a = [1, 2] 

b = [1, 4]

Output:

For custom output: 1

For the function: return value 1

Here a = [1, 2], b = [1, 4] -> Array after merging a and b = [1, 1, 2, 4]. Median = Min(1, 2) = 1

Notes

Input Parameters: The function takes 2 arguments, an integer array arr and an integer array brr.

Output: Return a single integer, denoting the median of the array (arr + brr) obtained after merging the arrays arr and brr.

Constraints:

● 2

● 1

Solutions:

We provided two solutions

1) linear_solution.java

● We have to find the median of the merged array obtained after merging 2 sorted arrays.

● We start by traversing the 2 array and keeping track of the minimum element so far.

● As we can see, the answer would be the (n+m)/2 th minimum element.

● So, we keep on traversing the arrays and move the current pointer for the array having the smaller element, to the next element. 

● Finally, when we reach the (n+m)/2 th element, we return it, as it is our answer.

Time Complexity:

O(n+m) considering the length of a is n and length of b is m.

We simply traverse both the arrays simultaneously and keep on checking for the minimum element. We traverse at most one time. Hence, the time complexity is O(n+m).

Auxiliary Space Used:

O(1)

We do not use any extra memory except for initializing several variables.

Space Complexity:

O(n+m) considering the length of a is n and length of b is m.

Input complexity is O(n+m), auxiliary space used is O(1), and output space complexity is O(1), hence total complexity will be O(n+m).


2) optimal_solution.java

● We have to find the median of the merged array obtained after merging 2 sorted arrays.

● The goal is to find a partition that divides the combined array in 2 equal halves (1 half having 1 more element than other in case of odd length) such that the elements in the first half are smaller or equal to the elements in the second half.

● Once we have such a partition, we can simply return the largest element of the first partition which would be the desired output as that would be the element present at the (n+m-1)/2th index in the merged array (arr + brr) which is the required answer.

● We use binary search to find such a partition and we start by initializing 2 pointers min_index = 0 and max_index = Math.min(n,m).

● We start iterating over the arrays and compare the last element of partition 1 present in array arr to the first element of partition 2 present in array brr and vice versa. After each comparison, we update min_index and max_index accordingly.

● Finally, we keep on repeating this until min_index

● And we find the median when either we exhaust one of the arrays or none of the if conditions are met.

Example:

● Let's try to find out the median for a = [1,2,5], b = [1,2,3,4,5]

● So initially min_index = 0, max_index = n = 3.

● Now we start iterating until min_index

● So, now during first iteration, i = 1 and j =  3

● b[2] = 3 and a[1] = 2, so here b[2]>a[1] => min_index = i+1 = 2.

● So during iteration 2, i = 2 and j = 2

● So in this case we go to the else condition as none of the if conditions are true.

● Hence we return Max(a[1],b[1]) = Max(2,2) = 2.

● So the median is 2. 

Time Complexity:

O(Log(Min(n,m)) considering the length of a is n and length of b is m.

We use binary search to find the partition. Also, since we are performing binary search until we find the median or we exhaust one of the arrays, time complexity is O(Log(Min(n,m)).

Auxiliary Space Used:

O(1)

We do not use any extra memory except for initializing several variables.

Space Complexity:

O(n+m) considering the length of a is n and length of b is m.

Input complexity is O(n+m), auxiliary space used is O(1), and output space complexity is O(1), hence total complexity will be O(n+m).

Attend our Free Webinar on How to Nail Your Next Technical Interview

Recommended Posts

All Posts