Median of Two Sorted Arrays
Hard · Binary Search · Array · Binary Search · Divide and Conquer
Problem
nums1 and nums2 are each sorted in non-decreasing order. Return the median of all their values taken together. When the total count is odd, that is the middle value; when it is even, it is the average of the two middle values, so it can be a fraction such as 2.5.
Either array may be empty (but not both), and the same value can appear in both. The goal is O(log(m + n)) time: find the middle without merging the arrays.
LeetCode caps each array at 1,000 values. Here they go up to 2,000,000, so that the stress tests show the difference between walking the arrays and binary searching them. Answers within 10^-6 are accepted.
Examples
Input: nums1 = [1,3], nums2 = [2] Output: 2.0
Together the values are 1, 2, 3, and the middle one is 2.
Input: nums1 = [1,2], nums2 = [3,4] Output: 2.5
Together they are 1, 2, 3, 4. The two middle values are 2 and 3, and their average is 2.5.
Constraints
- 0 <= len(nums1), len(nums2) <= 2 * 10^6 (LeetCode: 1,000)
- 1 <= len(nums1) + len(nums2)
- -10^7 <= nums1[i], nums2[i] <= 10^7 (LeetCode: 10^6)
- both arrays are sorted in non-decreasing order
Approaches
- Merge, then take the middle — time O(m + n), space O(m + n)
Related problems
Start free on Cariara · Coding problems · System design studio
