You get two sorted arrays of integers, nums1 and nums2. Return the median of all their numbers together.
The median is the middle number when all the numbers are in order. With an even count, there are two middle numbers. Then the median is their average.
Each array goes from smallest to largest. One of them can be empty, but not both.
The tests keep a few big arrays. They call your solution on many pairs of them. Don't change the arrays you get.
Each answer is printed with one digit after the point, like 9.0 or 2.5.
Example 1:
Input: nums1 = [4,9,15], nums2 = [6,11] Output: 9.0 Explanation: Sorted together, they make [4,6,9,11,15]. The middle one is 9.
Example 2:
Input: nums1 = [-5,0,3,8], nums2 = [1,2,12,20] Output: 2.5 Explanation: Sorted together, they make [-5,0,1,2,3,8,12,20]. The two middle ones are 2 and 3. Their average is (2 + 3) / 2 = 2.5.
Example 3:
Input: nums1 = [], nums2 = [7,10] Output: 8.5 Explanation: nums1 is empty. The median of 7 and 10 is (7 + 10) / 2 = 8.5.
Constraints:
- Each array has 0 to 100,000 numbers.
- At least one of them is not empty.
- Each number is from -106 to 106.
- Both arrays are sorted from smallest to largest.
- One test makes up to 10,000 calls.
Your solution should run in O(log(min(m, n))) time, where m and n are the two lengths.
Picture a cut through each array. The two left parts together hold half of all the numbers. If no number on the left is bigger than a number on the right, the median sits at the cut.
Say the left part takes
i numbers from the shorter array. The rest of the half comes from the other one. Binary search on i. When the shorter array's last left number is too big, i is too big.
Each try halves the range of
i, which starts as 0 to the shorter length: O(log(min(m, n))) time.A merge of the two arrays would take O(m + n) time for each call. With 10,000 calls, that is too slow.
Only a few numbers are kept, so the extra space is O(1).
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
