Median of Two Sorted Arrays
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Find the median of two sorted lists as if they were merged, in O(log(m + n)).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Merging is O(m + n). What property must the lower half satisfy?
- Hint 2Take i numbers from the first list and the remaining half-count from the second, then check the two cross conditions.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Two queues of people, each already sorted by height, are to be split into a "shorter half" and a "taller half" of equal size (that is the median idea). Decide how many people the first queue gives to the shorter half; the second queue then gives the rest. The split is right when the tallest person in the shorter half is not taller than the shortest person in the taller half, in both queues. If the first queue's shorter-half tallest is too tall, give fewer from it; otherwise give more.
- The obvious way
Merge both lists and take the middle: O(m + n).
- The key insight
Cut the first list after i numbers and the second after (half - i) numbers, so the left parts hold half of everything. The cut is correct when the last number on each left side is not bigger than the first number on the other right side. If the first list's left end is too big, cut earlier; if the second's is too big, cut later. Binary search i on the shorter list. The median comes from the numbers at the cut.
- The algorithm
- Search on the shorter list. Total count tells the half-size.
- Guess the cut: i numbers from the short list, half - i from the long one.
- Read the four numbers around the cut (use -infinity / +infinity beyond the ends).
- Cut valid? Compute the median from them. Short list's left too big? Cut earlier. Otherwise cut later.
Watch it run
Examplefirst = [1, 3], second = [2]
Three numbers in total, so the lower half should hold 2. Search on the shorter list [2]. Try giving 0 of its numbers to the lower half.
cut: 0 from [2], 2 from [1, 3]
Where people slip
- Always search on the shorter list so the second cut never goes negative.
- Use +-infinity for neighbours beyond the ends instead of special cases.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def find_median_sorted_arrays(first, second):
if len(first) > len(second):
first, second = second, first # search on the shorter list
m, n = len(first), len(second)
half = (m + n + 1) // 2
low, high = 0, m
while low <= high:
cut_first = (low + high) // 2 # how many we take from first
cut_second = half - cut_first # and from second
first_left = first[cut_first - 1] if cut_first > 0 else float("-inf")
first_right = first[cut_first] if cut_first < m else float("inf")
second_left = second[cut_second - 1] if cut_second > 0 else float("-inf")
second_right = second[cut_second] if cut_second < n else float("inf")
if first_left <= second_right and second_left <= first_right: # valid cut
if (m + n) % 2 == 1:
return max(first_left, second_left)
return (max(first_left, second_left) + min(first_right, second_right)) / 2
if first_left > second_right:
high = cut_first - 1 # took too many from first
else:
low = cut_first + 1Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.