4. Median of Two Sorted Arrays
Asked at Google, Meta, Amazon, Apple and 5 more
Difficulty
Hard
Time
O(log(min(m, n)))
Space
O(1)
Pattern
Array
Companies
9
Problem
You are given two arrays, nums1 and nums2, and each one is already sorted in increasing order. Imagine merging them into one big sorted array. Your job is to return the median of that merged array.
The median is the middle value. If the total number of elements is odd, the median is the single middle element. If the total is even, there is no single middle element, so the median is the average of the two middle elements.
You must not actually build the merged array. The expected solution runs in O(log(min(m, n))) time, where m and n are the two array lengths. The trick is to binary search for the correct split point instead of merging. One array may be empty, and the two arrays may have very different sizes.
Median of the merged array
Constraints
- ●
nums1.length == m - ●
nums2.length == n - ●
0 <= m <= 1000 - ●
0 <= n <= 1000 - ●
1 <= m + n <= 2000 - ●
-10^6 <= nums1[i], nums2[i] <= 10^6
Examples
nums1 = [1,3], nums2 = [2]2.00000nums1 = [1,2], nums2 = [3,4]2.50000Asked At
9 companies| 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 → |
| Bloomberg | Hard | View all Bloomberg questions → |
| Goldman Sachs | Hard | View all Goldman Sachs 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.
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).
Binary search on the split point
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
O(log(min(m, n))) timedef 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 runs in O(log(min(m, n))) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Median of Two Sorted Arrays?
Median of Two Sorted Arrays is asked at Google, Meta, Amazon, Apple, Microsoft, Rippling, Walmart, Bloomberg, Goldman Sachs. 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.