Find the median of two sorted arrays in O(log(min(m, n))) by binary searching the partition point. One of the hardest classic FAANG questions, explained.
The problem
a and b are sorted ascending (not both empty). Return the median of all their values as a float. Target: O(log(min(m, n))).
Examples
Example 1
Input
median_sorted([1, 3], [2])
Expected output
2.0
Example 2
Input
median_sorted([1, 2], [3, 4])
Expected output
2.5
+ 5 hidden tests on Submit.
Edge cases to ask about
- One array empty
- All values equal
- Very different lengths
Hints
0/3How an interviewer scores this
0/9Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.
Complexity Lab
What does this cost as n grows?
Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and measure your code against the optimal one at growing input sizes.
Pick both to reveal the answer.
Measure it
Runs the function on inputs of size 250 up to 16,000 and records the time and peak memory. Slow solutions stop early — a short curve is itself the answer.
From brute force to optimal
The progression an interviewer wants to hear, one step at a time.
| Approach | Time | Space | Idea |
|---|---|---|---|
| Merge and pick the middle | O(m + n) | O(m + n) | |
| bestBinary search the partition of the smaller array | O(log min(m, n)) | O(1) | A valid split has every left value ≤ every right value. |
Walkthrough of the optimal approach (try it yourself first)
Cut a after i elements and b after j = half − i, so the left side holds half of all values. The cut is right when a[i−1] ≤ b[j] and b[j−1] ≤ a[i]. Then the median comes from the max of the left side (and the min of the right side, for even totals).
If a[i−1] > b[j] you took too many from a: move left. Otherwise move right. Searching over the shorter array keeps j in range. ±∞ sentinels handle the edges.
Complexity: O(log min(m, n)) time, O(1) space. The binary search runs over the shorter array's possible cut positions only.
Reveal the reference solution
def median_sorted(a, b): if len(a) > len(b): a, b = b, a m, n = len(a), len(b) half = (m + n + 1) // 2 lo, hi = 0, m while lo <= hi: i = (lo + hi) // 2 # elements taken from a j = half - i # elements taken from b a_left = a[i - 1] if i > 0 else float("-inf") a_right = a[i] if i < m else float("inf") b_left = b[j - 1] if j > 0 else float("-inf") b_right = b[j] if j < n else float("inf") if a_left <= b_right and b_left <= a_right: if (m + n) % 2: return float(max(a_left, b_left)) return (max(a_left, b_left) + min(a_right, b_right)) / 2 if a_left > b_right: hi = i - 1 else: lo = i + 1
The brute force, for comparison
def median_sorted(a, b): merged = sorted(a + b) k = len(merged) mid = k // 2 return float(merged[mid]) if k % 2 else (merged[mid - 1] + merged[mid]) / 2
Follow-ups interviewers ask
- k-th smallest element of the two arrays.
Frequently asked interview questions
Core interview concepts, complexities, and follow-ups scored by hiring teams.
What is the time complexity of Median of Two Sorted Arrays in Python?
The optimal solution runs in O(log min(m, n)) time and O(1) auxiliary space. The binary search runs over the shorter array's possible cut positions only.
What is the brute-force approach, and how do you optimise it?
Merge and pick the middle: O(m + n) time, O(m + n) space. Binary search the partition of the smaller array: O(log min(m, n)) time, O(1) space. A valid split has every left value ≤ every right value.
What follow-up questions do interviewers ask about Median of Two Sorted Arrays?
k-th smallest element of the two arrays.