The problem
Given two sorted lists, find the median of all their numbers combined, in O(log(m + n)) time.
Input: A = [1, 3, 8, 9, 15], B = [7, 11, 18, 19, 21, 25] Output: 11
Picture it
Picture two sorted bookshelves. The median splits all books into a smaller half and a larger half. We make one cut in each shelf so that the left pieces together hold exactly half the books. The cut is right when every book left of both cuts is ≤ every book right of both cuts. We binary search where to cut the shorter shelf; the other cut follows automatically.
How to recognise it
- Two lists are already sorted and you need an order statistic (the median, or the k-th smallest) of their combination.
- The required time is O(log(m + n)), which rules out merging the lists, even though merging is easy.
- The median splits the combined numbers into a left half and a right half of known sizes. Choosing how many items come from the first list decides how many come from the second, so there is only one number to search for: the cut position in the shorter list.
Start with brute force
Combine the lists, sort, and read the middle.
def median_brute(a, b):
c = sorted(a + b)
k = len(c)
if k % 2:
return c[k // 2]
return (c[k // 2 - 1] + c[k // 2]) / 2
This is O((m + n) log(m + n)) time and O(m + n) space; a two-pointer merge brings it to O(m + n). With at most 1,000 numbers per list it runs instantly, but the problem asks for logarithmic time: about log2(1,000) ≈ 10 cut positions need checking, not 2,000 items.
From brute force to the idea
- Find the waste. To find the middle you only need to know where the halves split, not the full merged order.
- Cut both lists. Take
iitems fromaandjfrombfor the left half. The left half must havehalf = (m + n + 1) // 2items, soj = half - i. The+ 1puts the extra item on the left when the total is odd. - Check the cut with four values. The cut is correct when every left item is at most every right item. Each list is sorted, so only the edges matter:
a_left <= b_rightandb_left <= a_right. A missing edge (cut at the very start or end) counts as-inforinf. - Move the cut. If
a_left > b_right, too many items came froma:hi = i - 1. Otherwiseb_left > a_right, so too few came froma:lo = i + 1. - Read the median. For an odd total it is the largest left item,
max(a_left, b_left). For an even total it is the average of that and the smallest right item. - Search the shorter list. The first lines swap so that
ais shorter. Thenj = half - ialways stays between 0 and n.
This is the key idea: binary search the cut position in the shorter list, and check it using the four values next to the two cuts.
The key idea
Binary search a partition of the shorter list; check maxLeft ≤ minRight on both sides. O(log(min(m, n))).
Python solution
def median(a, b):
if len(a) > len(b):
a, b = b, a
m, n = len(a), len(b)
lo, hi, half = 0, m, (m + n + 1) // 2
while lo <= hi:
i = (lo + hi) // 2 # cut in a
j = half - i # matching cut in b
a_left = a[i - 1] if i > 0 else -inf
a_right = a[i] if i < m else inf
b_left = b[j - 1] if j > 0 else -inf
b_right = b[j] if j < n else inf
if a_left <= b_right and b_left <= a_right:
if (m + n) % 2:
return 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 + 1LeetCode adds the imports for you. To run this on your own machine, put this at the top: from math import inf
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O((m + n) log(m + n)) with sorting, O(m + n) with a merge | O(m + n): the combined list |
| Partition search (shown code) | O(log min(m, n)): the cut range in the shorter list halves each step | O(1): a few numbers |
Edge cases
- Imports: the shown code uses
infwithout importing it, so it needsfrom math import inf; otherwise the first comparison raisesNameError. - The example: returns 11.
- One list empty (
[]and[2, 3]):ais empty,iis 0, and the result is 2.5. - Return type: an odd total returns an element as is (an
intfor integer input, such as11), and an even total returns a float. LeetCode accepts both. - All equal (
[2, 2]and[2, 2]): the first cut is already valid; returns 2.0. - Both lists empty: the problem rules this out. The shown code would compute
(-inf + inf) / 2and returnnan.
Common mistakes
- Skipping the swap. With
alonger,jcan go negative, and Python's negative indexing reads from the end ofbinstead of failing. - Using
half = (m + n) // 2but still returning the left maximum for an odd total. For[1, 3]and[2]the median then comes out as 1 instead of 2. - Forgetting the
-infandinfguards, so a cut at either end of a list raisesIndexError.
Return the k-th smallest number (k counts from 1) of the two sorted lists combined, in O(log min(m, n)). For [1, 3, 8] and [2, 4] with k = 4 the answer is 4. Describe your approach, then write it if you like.
Compare with our answer
Use the same cut, but the left part now has exactly k items, so j = k - i. The cut in a must also leave j between 0 and n, which bounds the range: lo = max(0, k - n) and hi = min(k, m). The answer is the largest item on the left.
from math import inf
def kth(a, b, k): # k counts from 1
if len(a) > len(b):
a, b = b, a
m, n = len(a), len(b)
lo, hi = max(0, k - n), min(k, m)
while lo <= hi:
i = (lo + hi) // 2
j = k - i
a_left = a[i - 1] if i > 0 else -inf
a_right = a[i] if i < m else inf
b_left = b[j - 1] if j > 0 else -inf
b_right = b[j] if j < n else inf
if a_left <= b_right and b_left <= a_right:
return max(a_left, b_left)
if a_left > b_right:
hi = i - 1
else:
lo = i + 1
The median is then kth of the middle position (or the average of the two middle positions).
A strong answer mentions: why the range for i must be clipped to max(0, k - n)..min(k, m), that the answer is the left maximum, and the O(log min(m, n)) cost.
1. Two servers each keep a sorted list of response times, and you need the 90th-percentile time across both. Which approach fits best?
A percentile is a k-th smallest query, and the partition search answers it in O(log min(m, n)). Merging until position k is O(k), and averaging two percentiles is not the percentile of the combined data.
2. Why does the shown code use half = (m + n + 1) // 2 for the left half?
With the extra item on the left, an odd total's median is exactly max(a_left, b_left). For an even total the + 1 changes nothing, and the median averages the two sides.
3. A learner deletes the first two lines that swap a and b. Which call now returns a wrong answer?
With a much longer, a cut of i = 4 gives j = -1, and b[-1] silently reads the 6, so the code accepts a wrong cut and returns 4.5. In the other calls the lists are close enough in length that j stays within 0 to n.
Score 60% or more and the lesson is marked complete.