Katkat
Back

Combined Median of Two Sorted Integer Lists in Logarithmic Time

ByteDanceMachine Learning Engineer · Technical Screen
HardMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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

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

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

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

Input: nums1 = [], nums2 = [6, 11]
Output: 8.5

The two values are 6 and 11, and their mean is 8.5.