#4 Median of Two Sorted Arrays
frequently reported atAdobeGoldman SachsBloombergAmazonMicrosoftGoogle
the problem
In plain words
Given two sorted arrays of sizes m and n, return the median of all m + n values. Required: O(log(m + n)).
in nums1 = [1,3], nums2 = [2]
out 2.0
in nums1 = [1,2], nums2 = [3,4]
out 2.5
- 0 ≤ m, n ≤ 1000
- 1 ≤ m + n ≤ 2000
- -10⁶ ≤ values ≤ 10⁶
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternModified binary search
The median splits all values into a left half and a right half. If the shorter array gives i elements to the left half, the other gives half − i. Binary search i until every left value ≤ every right value.
solutions
From brute force to optimal
Merge the two sorted arrays like merge sort, then read the middle.
- Two-pointer merge into a new array.
- Odd length → middle; even → average of the two middles.
Every element is copied once.
The merged array.
class Solution { public double findMedianSortedArrays(int[] a, int[] b) { int[] all = new int[a.length + b.length]; int i = 0, j = 0, k = 0; while (i < a.length && j < b.length) all[k++] = a[i] <= b[j] ? a[i++] : b[j++]; while (i < a.length) all[k++] = a[i++]; while (j < b.length) all[k++] = b[j++]; int n = all.length; if (n % 2 == 1) return all[n / 2]; return (all[n / 2 - 1] + (double) all[n / 2]) / 2.0; }}Run the same merge but only count up to the middle, remembering the last two values.
- Advance the smaller head (m + n)/2 + 1 times.
- Keep
prevandcur. - Odd → cur; even → (prev + cur) / 2.
Walks half of all elements.
No merged copy.
class Solution { public double findMedianSortedArrays(int[] a, int[] b) { int n = a.length + b.length; int i = 0, j = 0, prev = 0, cur = 0; for (int step = 0; step <= n / 2; step++) { // walk the merge, remember the last two values prev = cur; if (j >= b.length || (i < a.length && a[i] <= b[j])) cur = a[i++]; else cur = b[j++]; } return n % 2 == 1 ? cur : (prev + (double) cur) / 2.0; }}Choose how many elements of the shorter array go left; check the four border values.
- Make
athe shorter array; half = (m + n + 1) / 2. - Binary search i in [0, m]; j = half − i.
- Borders: aLeft = a[i−1], aRight = a[i], bLeft = b[j−1], bRight = b[j] (±∞ off the ends).
- aLeft ≤ bRight and bLeft ≤ aRight → done. aLeft > bRight → i too big; else i too small.
- Median = max(lefts) if odd, else (max(lefts) + min(rights)) / 2.
Binary search over i in the shorter array only.
A handful of integers.
class Solution { public double findMedianSortedArrays(int[] a, int[] b) { if (a.length > b.length) return findMedianSortedArrays(b, a); // search the shorter array int m = a.length, n = b.length; int half = (m + n + 1) / 2; // size of the left half int lo = 0, hi = m; // i = how many elements of a go left while (lo <= hi) { int i = lo + (hi - lo) / 2; int j = half - i; // the rest of the left half comes from b int aLeft = i == 0 ? Integer.MIN_VALUE : a[i - 1]; int aRight = i == m ? Integer.MAX_VALUE : a[i]; int bLeft = j == 0 ? Integer.MIN_VALUE : b[j - 1]; int bRight = j == n ? Integer.MAX_VALUE : b[j]; if (aLeft <= bRight && bLeft <= aRight) { // every left value <= every right value if ((m + n) % 2 == 1) return Math.max(aLeft, bLeft); return (Math.max(aLeft, bLeft) + (double) Math.min(aRight, bRight)) / 2.0; } if (aLeft > bRight) hi = i - 1; // took too many from a else lo = i + 1; // took too few from a } throw new IllegalArgumentException("inputs must be sorted"); }}in the room
How to say it in the interview
talk track
- Start with merge (O(m+n)) to show you understand the median, then say the O(log) target forces a partition search.
- Draw the two arrays with a vertical cut through each; label the four border values.
- Explain why we search the shorter one: it keeps j = half − i inside [0, n].
traps
- Searching the longer array: j can go negative.
- Integer division when averaging: use
/ 2.0and cast to double before adding. - Forgetting the ±∞ sentinels when i or j is 0 or at the end.
what they ask next
Follow-ups
k-th smallest of two sorted arrays?
Same partition idea with half replaced by k, or a recursive "drop k/2 elements" approach in O(log k).
before you submit
Edge cases to test
- One array is empty.
- All of one array is smaller than all of the other.
- Even total: average the two middles with / 2.0, not / 2.
practise next
Similar problems
- #21Merge Two Sorted ListsEasyin Linked Lists
- #295Find Median from Data StreamHardin Heaps