Median of Two Sorted Arrays.

Median of two sorted arrays.

URL : https://leetcode.com/problems/median-of-two-sorted-arrays/

Given two sorted arrays of different sizes, find the median of the combined sorted array.

Median Definition : https://en.wikipedia.org/wiki/Median

Input: nums1 = [1,3], nums2 = [2]

Output: 2.00000

Explanation: merged array = [1,2,3] and median is 2

Approach 1:

Store all the elements of the two arrays into a final array.

Sort the array.

Return the median.

Time Complexity = O((n+m)log(n+m))

Space Complexity = O(n+m)

Can we do better? Yes.

Approach 2:

Use the concept of merge sort to merge the arrays into a new final array.

Return the median.

Time Complexity = O(n+m)

?Space Complexity = O(n+m).

Can we still do better? Yes.

What do we need to find the median? It’s the middle element (in case total number of elements is odd) and (middle, middle+1) element if total number of elements is even.

Note: middle = (n+m)/2.

Approach 3:

Use the concept of merge sort to merge the arrays into a new final array.

Maintain a counter keeping track of the number of elements traversed.

?????????????When counter == middle => store the middle and (middle+1) element.

?????????????Return median.

Time Complexity = O(n+m)

Space Complexity = O(1).

Can we still do better? Answer is again yes.

We know that in the resultant array, all elements to left are less, and all elements to the right are greater than median.

Since arrays are sorted, can’t we make use of this fact? Yes, we can.

Let us partition the arrays in such a way that all the elements from both the arrays to the left are less than or equal to all the elements from both the arrays to the right.

If we can get such partition, we can easily tell the median.

For such a partition, following conditions should be true:

1)?????No of elements to left = No of elements to right.

2)?????Arr1[middle] <= Arr2[middle+1] && Arr2[middle] <= Arr2[middle+1].

i.e., ai <= bj+1 && bj <= ai+1

Finally median = (max (ai, bj) + min (ai+1, bj+1))/2?????if(total no of elements is even)

????????????????else = max (ai, bj)????????????????????????????????????????????if(total no of elements is odd)

We know,

total elements = n+m

=> elements to left = elements to right = (n+m)/2

=> if mid1 = partition for first array and mid2 = partition for second array, mid1+mid2 = (m+n)/2

Approach 4: (Best Solution)

Do binary search based on number of elements to keep on left and right of array.

?????????????low = 0, high = Arr1.size()

while (low <= high)

????????????? mid1 = (Low+ high)/2?????// number of elements to left in array1

???????????? ? mid2 = (total elements)/2 – mid1??// number of elements to left in array2

????????????? left1 = Arr1[mid-1], right1 = Arr1[mid]

????????????? left2 = Arr2[mid2-1], right2 = Arr2[mid2]

????????????? if(left1 <= right2 && left2 <= right1) // means we have found the partition????????????

????????????????????????????if(total elements is even)

??????????????????????????????????????????Median = (max(left1, left2) + min(right1, right2))/2

????????????????????????????else

??????????????????????????????????????????Median = max(left1, left2)

????????????? if(left1 > right2)????// means we have came more towards right, so shift focus to left

????????????????????????????high = mid1-1;

?????????????else

????????????????????????????low = mid1+1;???// means we have came more towards left, so shift to right.

Return median.

Time Complexity = O(log(min(n,m))

Space Complexity = O(1).

Solution Link : https://gist.github.com/shreyansh-sinha/7867d3a53e8bfa03e79b7fe87b1628a7/