LeetCode: Median of Two Sorted Arrays: explanation and solution with C++/Java/Python
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))$.
You may assume nums1 and nums2 cannot be both empty.
To find the median of an array, there are two sub-cases here according to the size of array(assume index start from 0):
It’s will be comre complicated to compute the median of two array.
We can merge the two array into one array, keep the sorted property of array. The time complexity for this will be $O(max(m, n))$, with a constant time for computing the median.
Optimization to log(m+n)
For almost any algorithms which perform on array and complexity is $O(logN)$, we need to split the size into almost
size/2 during every iteration. Think about the binary search for a sorted array, it’s complexity is $O(logN)$.
If we could find an algorithm which find the Kth largest element in two sorted array, then use a split strategy we could come out this pseudocode:
Find Kth largest in one sorted array
Algorithm design guide:
Try to solve a similar but much easy case, then expand it into harder cases.
Let’s first solve this much easier and similar problem. Like the Binary Search algorithm, we first check the compare result of
(size/2) >= K, we can drop the right part of array. Otherwise we can drop the left part and find
K-(size/2+1) th in right part of this array.
The fundamental idea is reducing the size to half in every iteration.
Find Kth largest in two sorted array, without merging
This problem is similar with
Kth largest in one array, but non-trivial.
There are 4 sub-cases which depends on the compare result of
B[n/2]. Let’s assume
i = m/2 and
j = n/2,
A[i] <= B[j].
(i+j) >= K, this means there are more than
K elements in left part of two array, so we can drop the right part of B. Otherwise, if
(i+j) < K, we can drop the right part of A and try to find the
K-(m/2+1) th largest in left parts.
In this algorithm we almost reduce 1/4 of the total size of two array. The complexity analysis is very hard for most programmers. Chapter “A Selection Problem” of Pearls of Functional Algorithm Design contains the detail description.
This is C version solution, take the advantage of pointer, the parameter of “int A” with index operation “A+index” point to sub-array, this save two parameters in findMedianSortedArrays. For C++ version, we need to add a start index for array, similar with below Java solution.
Be careful with those index in edge cases!
Preparing for an interview? Checkout this!