LeetCode – Median of Two Sorted Arrays Java Solution

Tags: , , , ,

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

Example 2:

Analysis

It is easy to come up with a O(n) solution. Then it is high likely that the interviewer will ask you to give the algorithm with time complexity O(logn). 

For any problem with sorted array, to come up with a O(logN) solution, we should consider the binary search related algorithm. 

To find the median value of an array, if the array is even, we have to find the two values in the middle. We can solve the problem by adopting the method of getting the Kth number in two sorted arrays.  

Suppose array A and array B’s length are LA and LB respectively, 

If LA + LB is not even, we just find the (LA + LB) / 2 th element.

If LA + LB is even, we need to find the (LA + LB) / 2 - 1 and (LA + LB) / 2 th elements, then the average is the answer.

Given two sorted array, how to find the Kth element in O(logN) time?

Here, K means the index. So for 1first smallest element, K == 0. For 2nd smallest element, K == 1, et al. 

We can divide K into two parts:  K1 and K2, such that K1 + K2  = K – 1.

The following examples show why K2 == K - K1 - 1?

For instance if K = 1, (e.g.,  we want to find the 2nd smallest element), if K1 == 0, then K2 == 1 – 0 – 1 == 0.

if K == 2, (e.g., we want to find the 3rd smallest element) and if  K1 == 0, then K2 == 2 – 0 – 1 = 1.  This means we can just consider A[0] and B[0 .. 1] to get the 3rd smallest element. 

The algorithm of adopting binary search to get the Kth element 

If A[K1] <= A[K2], we know that A[0 .. K1] must be smaller than the Kth element, and B[K2 + 1, B.length - 1] must be larger than the Kth element. Then it will be safe to remove the elements in A[0 .. K1], and B[K2 + 1, bLength - 1] . In the remaining set, we just need to find the ( K - ( K1 + 1)) th element. 

Similarly, we can deal with the case with A[K1] > A[K2].

How to choose K1 and K2 safely?

We need to make sure K1 is in the range [0 .. A.length - 1], as here will be an index error if K1 is larger than A.length - 1

Similarly, we need to make sure K2 is in the range [0 .. B.length - 1].

We can divide K proportionally with LA and LB. e.g., K1 = k * LA / (LA + LB), so K2 = K - K1 - 1

The following is the solution in Java.