Median of Two Sorted Arrays
You get two lists of integers, nums1 and nums2, each sorted from smallest to largest and holding at least one value. Return the median of all their values together, as text.
For an odd total count the median is the middle value, such as "4". For an even count it is the average of the two middle values, such as "2.5" or "-0.5". Write a whole number without a decimal point, and zero as "0", never "-0". Aim for O(log(min(m, n))) time.
Function
- nums1integer-array
- the first list, sorted from smallest to largest
- nums2integer-array
- the second list, sorted from smallest to largest
- Returnsstring
- the median of all the values, as text such as "4" or "-2.5"
Constraints
1 ≤ nums1.length, nums2.length ≤ 3000-106 ≤ nums1[i], nums2[i] ≤ 106- Both lists are sorted in non-decreasing order, and values may repeat.
Examples
- Input
- nums1 = [1, 4]nums2 = [2, 7, 9]
- Output
- "4"
- Explanation
- Together the values are 1, 2, 4, 7, 9. Five values have one middle value, the third, which is 4.
- Input
- nums1 = [1, 2]nums2 = [3, 4]
- Output
- "2.5"
- Explanation
- Together the values are 1, 2, 3, 4. The two middle values are 2 and 3, their sum is 5, and half of 5 is 2.5.
- Input
- nums1 = [-7, -3]nums2 = [-2, 0]
- Output
- "-2.5"
- Explanation
- Together the values are -7, -3, -2, 0. The middle values -3 and -2 add up to -5, and half of -5 is -2.5.
Follow-up
Can you use the same cut to find the k-th smallest value of the two lists, for any k, in logarithmic time?
Hints
Open them one at a time. Each one gives away a little more.
Merging the two lists finds the median in
O(m + n). To do better, think of the median as a cut: a line that splits allm + nvalues into a lower half and an upper half of the same size.The lower half is a prefix of
nums1plus a prefix ofnums2. If it takesivalues fromnums1, the count fromnums2follows. The cut is right when the last value taken from each list is no bigger than the first value left in the other one.Binary search on
iover the shorter list. If the last value taken fromnums1is too big, take fewer from it; if the last value taken fromnums2is too big, take more. At the right cut the median comes from the largest value below the cut and the smallest above it. Add those two integers and halve the sum yourself.
Solution
Merging the lists gives the median in O(m + n), but most values it reads cannot change the answer. The median depends only on where the cut between the lower and upper half falls, and one number fixes that cut: how many values the lower half takes from the shorter list. Binary search finds it in O(log(min(m, n))) steps.
Merge the two lists
Intuition
Merge the lists the way merge sort does, into one sorted list merged. With total = m + n, add merged[(total-1)/2] and merged[total/2], using integer division. For an odd total both are the middle value, and for an even total they are the two middle values, so half the sum is the median either way.
Even if you stop at the middle, the merge steps over half the values, so the time is O(m + n).
Algorithm
- Merge the lists into
merged, always taking the smaller current value, then the rest of the list that is left. - With
total = m + n, addmerged[(total-1)/2]andmerged[total/2]. - Return half the sum as text: divide an even sum by 2; for an odd sum write the sign, half the absolute value, and
.5.
def half_text(total):
# total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
if total % 2 == 0:
return str(total // 2)
sign = "-" if total < 0 else ""
return sign + str(abs(total) // 2) + ".5"
def findMedianSortedArrays(nums1, nums2):
# Merge the two sorted lists into one, the way merge sort does.
merged = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
merged.append(nums1[i])
i += 1
else:
merged.append(nums2[j])
j += 1
merged.extend(nums1[i:])
merged.extend(nums2[j:])
total = len(merged)
# For an odd total both indexes point at the one middle value.
return half_text(merged[(total - 1) // 2] + merged[total // 2])Binary search on the cut
Intuition
Let the lower half hold half = (m+n+1)/2 values, the extra one when the total is odd. It takes i values from the front of nums1 and j = half-i from the front of nums2. The cut is right when nothing below it is bigger than anything above it. Each list is sorted, so two checks remain: left1 ≤ right2 and left2 ≤ right1, where left is the last value a list gives the lower half and right the first value it keeps. A missing side counts as minus or plus infinity.
If left1 > right2, i is too big; if left2 > right1, it is too small. So i is a binary search over 0 to m. On [1, 2] and [3, 4], i = 1 fails on left2 = 3 > right1 = 2, and i = 2 passes: (2 + 3) / 2 = 2.5.
Algorithm
- Make
nums1the shorter list; lethalf = (m+n+1)/2. - Binary search
ifromlo = 0tohi = m, withj = half-i. - Read
left1 = nums1[i-1],right1 = nums1[i],left2 = nums2[j-1]andright2 = nums2[j], with infinity past an end. - If
left1 > right2, sethi = i-1. Ifleft2 > right1, setlo = i+1. - Otherwise, for an odd total return
max(left1, left2). For an even total, halvemax(left1, left2) + min(right1, right2)as text.
def half_text(total):
# total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
if total % 2 == 0:
return str(total // 2)
sign = "-" if total < 0 else ""
return sign + str(abs(total) // 2) + ".5"
def findMedianSortedArrays(nums1, nums2):
# Binary search over the shorter list.
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
half = (m + n + 1) // 2 # size of the left half; it gets the extra value when m + n is odd
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2 # values the left half takes from nums1
j = half - i # values it takes from nums2
# An empty side counts as minus or plus infinity.
left1 = nums1[i - 1] if i > 0 else float("-inf")
right1 = nums1[i] if i < m else float("inf")
left2 = nums2[j - 1] if j > 0 else float("-inf")
right2 = nums2[j] if j < n else float("inf")
if left1 > right2:
hi = i - 1 # too many values from nums1
elif left2 > right1:
lo = i + 1 # too few values from nums1
else:
left_max = max(left1, left2)
if (m + n) % 2 == 1:
return str(left_max)
return half_text(left_max + min(right1, right2))
return "" # not reached: sorted input always has a valid split
Pitfalls and edge cases
- Halving with floating point. Python prints a whole median as
3.0, and C's%fprints 2.5 as2.500000. Keep the sum an integer. - Writing the integer quotient and
.5for a negative odd sum.-1 / 2is 0 in C and Java, giving 0.5 for -0.5;-5 // 2is -3 in Python, giving -3.5 for -2.5. Halve the absolute value and put the sign back. - Writing
-0. Middle values -1 and 1 sum to 0, and the answer is"0". Take the sign from the sum. - Searching the longer list.
j = half-ican fall below 0 or passn. Swap the lists first. - Reading
nums1[i-1]wheni = 0, as on[9]and[1, 2]. Use infinities for missing values.
Frequently asked questions3
What is the time complexity of Median of Two Sorted Arrays?
The binary search on the cut takes O(log(min(m, n))) time and O(1) space, because each step halves the possible cuts in the shorter list. Merging takes O(m + n): for two lists of 3000, about 12 steps against 6000.
Why binary search on the shorter array?
Because j = half-i. With i over the shorter list, j stays between 0 and the longer list's length, so every read is in range or past an end you treat as infinity.
How do you return the median without floating point?
Add the two middle values as integers. Divide an even sum by 2. For an odd sum, write half its absolute value and .5, with a minus sign when the sum is negative: -1 becomes "-0.5".
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def findMedianSortedArrays(nums1, nums2):
# Write code hereTest #1
Test #2
Test #3
Arguments
nums1 = [1, 4] nums2 = [2, 7, 9]
Expected Output
"4"