# 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.

● 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 = 3 and a = 2, so here b>a => 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,b) = 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).

All Posts