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 algorithms 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 first. Like binary search algorithm, we first check the compare result of $(size/2)$ with K, if $(size/2) >= K$, we can drop the right part of array. Otherwise we can find $K-(size/2+1) th$ in right part of this array, and drop the left part.
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 can depends on the compare result of $A[m/2]$ and $B[n/2]$. Let’s assume $i = m/2$ and $j=n/2$, $A[i] <= B[j]$.
If $(i+j) >= K$, this means there are more then $K$ elements in left_part of two array, so we can drop right_part of B. Otherwise, if $(i+j) < K$, we can drop right_part of A, but 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
C / C++
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!