Median of Two Sorted Arrays
Asked at Google, Meta, Amazon, Apple, Microsoft, Rippling, Walmart
Problem
Given two sorted arrays, find the median of the combined sorted array in O(log(m+n)) time. This is one of the hardest commonly-asked FAANG problems and tests deep understanding of binary search on answer space.
Asked At
| Company | Difficulty | |
|---|---|---|
| Hard | View all Google questions → | |
| Meta | Hard | View all Meta questions → |
| Amazon | Hard | View all Amazon questions → |
| Apple | Hard | View all Apple questions → |
| Microsoft | Hard | View all Microsoft questions → |
| Rippling | Hard | View all Rippling questions → |
| Walmart | Hard | View all Walmart questions → |
How to Think About It
Brute force: merge both sorted arrays into one, then find the middle element. O(m+n) time. The interviewer will say "can you do better?" — the answer is O(log(min(m,n))).
Key insight: the median splits the combined array into two equal halves. You need to find the right partition point in the smaller array such that all elements on the left side are <= all elements on the right side.
How the partition works: pick a partition point i in nums1 (0 <= i <= m). The corresponding partition in nums2 is j = (m+n+1)/2 - i. This ensures the left half has exactly half the total elements. The left half is: nums1[0..i-1] and nums2[0..j-1]. The right half is: nums1[i..m-1] and nums2[j..n-1].
The validity check: max of left half <= min of right half. Specifically: nums1[i-1] <= nums2[j] AND nums2[j-1] <= nums1[i]. If both true, you found the correct partition. If nums1[i-1] > nums2[j], move i left. Otherwise move i right.
Why we binary search on the smaller array: the search space is 0..m where m is the smaller array size. Binary searching on the larger array would be slower. Always binary search on the smaller array.
Visual walkthrough for nums1=[1,3], nums2=[2]:
m=2, n=1. Total=3. Left half needs 2 elements.
Binary search on nums1 (smaller).
- lo=0, hi=2, i=1. j = (3+1)/2 - 1 = 1.
left: nums1[0]=1, nums2[0]=2. right: nums1[1]=3, nums2[1]=inf.
1 <= inf ✓, 2 <= 3 ✓. Valid partition.
Odd total: median = max(left) = max(1,2) = 2.
Result: 2.0
Edge cases: one array empty (median is middle of the other), arrays of different sizes (partition handles this automatically), all elements in one array are smaller (partition shifts to edge).
Optimal Approach
Step 1: Always binary search on the smaller array (swap if needed).
Step 2: Binary search range is [0, m] (can take 0 to all elements from smaller array).
Step 3: For each i, calculate j = (m+n+1)/2 - i.
Step 4: Find four border values:
- left_max1 = nums1[i-1] (or -inf if i=0)
- right_min1 = nums1[i] (or +inf if i=m)
- left_max2 = nums2[j-1] (or -inf if j=0)
- right_min2 = nums2[j] (or +inf if j=n)
Step 5: Check validity: left_max1 <= right_min2 AND left_max2 <= right_min1.
- If valid: median from border values.
- If left_max1 > right_min2: move hi = i-1 (too many from nums1).
- Else: move lo = i+1 (too few from nums1).
Step 6: For odd total, median = max(left_max1, left_max2). For even, average of max(left) and min(right).
Time: O(log(min(m,n))). Space: O(1).
What Trips People Up in Real Interviews
Merging the arrays and finding the median. That's O(n + m) and works, but the interviewer wants O(log(min(n, m))) using binary search.
Confusing "median" with "middle element." For odd-length combined arrays, it's the middle element. For even-length, it's the average of the two middle elements.
Not handling the case where one array is entirely before the other. If all elements of A are less than all elements of B, the median depends on the combined length.
Binary search on the shorter array. Always binary search on the smaller array to minimize the search space. If A is longer, swap them.
Using integer division for the partition formula without the +1 adjustment. j = (m + n + 1) // 2 - i handles odd total lengths correctly — using (m + n) // 2 gives the wrong partition.
Solution Code
def findMedianSortedArrays(nums1, nums2):
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2
j = (m + n + 1) // 2 - i
left_max = float('-inf') if i == 0 else nums1[i - 1]
right_min = float('inf') if i == m else nums1[i]
left_max2 = float('-inf') if j == 0 else nums2[j - 1]
right_min2 = float('inf') if j == n else nums2[j]
if left_max <= right_min2 and left_max2 <= right_min:
if (m + n) % 2 == 1:
return max(left_max, left_max2)
return (max(left_max, left_max2) + min(right_min, right_min2)) / 2
elif left_max > right_min2:
hi = i - 1
else:
lo = i + 1Frequently Asked Questions
What is the Median of Two Sorted Arrays problem?
Given two sorted arrays, find the median of the combined sorted array in `O(log(m+n)`) time. This is one of the hardest commonly-asked FAANG problems and tests deep understanding of binary search on answer space.
How do you solve Median of Two Sorted Arrays?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Median of Two Sorted Arrays?
Median of Two Sorted Arrays is asked at Google, Meta, Amazon, Apple, Microsoft, Rippling, Walmart. It is a hard difficulty problem.
What are common mistakes on Median of Two Sorted Arrays?
- Merging the arrays and finding the median. That's `O(n + m)` and works, but the interviewer wants `O(log(min(n, m)`)) using binary search.
- Confusing "median" with "middle element." For odd-length combined arrays, it's the middle element. For even-length, it's the average of the two middle elements.
- Not handling the case where one array is entirely before the other. If all elements of A are less than all elements of B, the median depends on the combined length.
- Binary search on the shorter array. Always binary search on the smaller array to minimize the search space. If A is longer, swap them.
- Using integer division for the partition formula without the +1 adjustment. j = (m + n + 1) // 2 - i handles odd total lengths correctly — using (m + n) // 2 gives the wrong partition.