Combined Median of Two Sorted Integer Lists in Logarithmic Time
Company: ByteDance
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given two integer arrays, `nums1` and `nums2`, each sorted in non-decreasing order. Return the median of all the values of both arrays taken together.
For `t` values in sorted order, the median is the middle value when `t` is odd, and the arithmetic mean of the two middle values when `t` is even.
Aim for a running time of `O(log(m + n))`, where `m` and `n` are the lengths of the two arrays.
### Function Signature
```python
def find_median(nums1: list[int], nums2: list[int]) -> float:
```
### Rules
- Duplicate values are counted separately, whether they occur within one array or across both arrays.
- Either array may be empty, but not both.
- Return a float. When the total number of values is even, return the exact mean of the two middle values, which may end in `.5`.
### Constraints
- `0 <= len(nums1) <= 1000` and `0 <= len(nums2) <= 1000`
- `1 <= len(nums1) + len(nums2) <= 2000`
- `-10^6 <= nums1[i], nums2[j] <= 10^6`
- Both arrays are sorted in non-decreasing order.
- Every possible answer is a multiple of `0.5` with absolute value at most `10^6`, so it is represented exactly as a float.
### Examples
**Example 1**
```text
Input: nums1 = [2, 9, 15], nums2 = [4, 11]
Output: 9.0
```
All values in order are `[2, 4, 9, 11, 15]`, and the middle one is `9`.
**Example 2**
```text
Input: nums1 = [-3, 1, 1], nums2 = [0, 5, 8]
Output: 1.0
```
All values in order are `[-3, 0, 1, 1, 5, 8]`, and the two middle values are `1` and `1`.
**Example 3**
```text
Input: nums1 = [], nums2 = [6, 11]
Output: 8.5
```
The two values are `6` and `11`, and their mean is `8.5`.
Overview: From a ByteDance technical screen for a machine learning engineer role: given two sorted integer arrays, return the median of all their elements combined, averaging the two middle values when the total count is even. It tests reasoning about sorted order under a logarithmic time target and edge cases such as an empty array.
You are given two integer arrays `nums1` and `nums2`, each sorted in non-decreasing order. Return the median of all the values of both arrays taken together, as a float.
For `t` values in sorted order, the median is the middle value when `t` is odd, and the arithmetic mean of the two middle values when `t` is even.
Aim for a running time of `O(log(m + n))`, where `m` and `n` are the lengths of the two arrays.
Rules:
- Duplicate values are counted separately, whether they occur within one array or across both arrays.
- Either array may be empty, but not both.
- Return a float. When the total number of values is even, return the exact mean of the two middle values, which may end in `.5`.
Constraints:
- `0 <= len(nums1) <= 1000` and `0 <= len(nums2) <= 1000`
- `1 <= len(nums1) + len(nums2) <= 2000`
- `-10^6 <= nums1[i], nums2[j] <= 10^6`
- Both arrays are sorted in non-decreasing order.
- Every possible answer is a multiple of `0.5` with absolute value at most `10^6`, so it is represented exactly as a float.
No value exceeds 2^31 - 1: every element, and the sum of the two middle values (at most 2 * 10^6 in absolute value), fits in a 32-bit signed integer.
Example 1:
Input: nums1 = [2, 9, 15], nums2 = [4, 11]
Output: 9.0
Explanation: All values in order are [2, 4, 9, 11, 15], and the middle one is 9.
Example 2:
Input: nums1 = [], nums2 = [6, 11]
Output: 8.5
Explanation: The two values are 6 and 11, and their mean is 8.5.
Constraints
- 0 <= len(nums1) <= 1000 and 0 <= len(nums2) <= 1000
- 1 <= len(nums1) + len(nums2) <= 2000
- -10^6 <= nums1[i], nums2[j] <= 10^6
- Both arrays are sorted in non-decreasing order.
- Every possible answer is a multiple of 0.5 with absolute value at most 10^6, so it is represented exactly as a float.
Examples
Input: ([2, 9, 15], [4, 11])
Expected Output: 9.0
Explanation: Source example 1: odd total 5; merged [2, 4, 9, 11, 15], middle value 9.
Input: ([-3, 1, 1], [0, 5, 8])
Expected Output: 1.0
Explanation: Source example 2: negatives and zero; merged [-3, 0, 1, 1, 5, 8], duplicate middles 1 and 1.
Hints
- The median depends only on the value or values at a fixed rank in the combined order, so think about which values must lie on the lower half without materialising the merged array.
- Either array may be empty and duplicates count separately: check that your boundary handling still works when one side contributes nothing to the lower half.
- When the total count is even, average the two middle values as a float, not with integer division, because the answer can end in .5 (including negative answers such as -0.5).