Skip to main content

4. Median of Two Sorted Arrays

hardAsked at Hugging Face

Find the median of two sorted arrays in O(log(m+n)) time. Hugging Face uses this to test binary search on abstract search spaces — a skill that transfers to efficiently finding threshold values in calibration curves for ML model confidence scoring.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Hugging Face loops.

  • Glassdoor (2025-11)— Reported in Hugging Face senior SWE onsite feedback as a hard binary search problem testing algorithmic depth.
  • Blind (2025-08)— Hugging Face threads cite this as a hard problem used for senior and staff-level engineering roles.

Problem

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Constraints

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • −10^6 <= nums1[i], nums2[i] <= 10^6

Examples

Example 1

Input
nums1 = [1,3], nums2 = [2]
Output
2.00000

Explanation: Merged array = [1,2,3], median is 2.

Example 2

Input
nums1 = [1,2], nums2 = [3,4]
Output
2.50000

Explanation: Merged array = [1,2,3,4], median is (2+3)/2 = 2.5.

Approaches

1. Merge then find median (O(m+n))

Merge both arrays into a sorted array and return the middle element (or average of two middle elements). Simple but doesn't meet the O(log(m+n)) requirement.

Time
O(m+n)
Space
O(m+n)
function findMedianSortedArrays(nums1, nums2) {
  const merged = [];
  let i = 0, j = 0;
  while (i < nums1.length && j < nums2.length) {
    if (nums1[i] <= nums2[j]) merged.push(nums1[i++]);
    else merged.push(nums2[j++]);
  }
  while (i < nums1.length) merged.push(nums1[i++]);
  while (j < nums2.length) merged.push(nums2[j++]);
  const mid = Math.floor(merged.length / 2);
  return merged.length % 2 === 1 ? merged[mid] : (merged[mid-1] + merged[mid]) / 2;
}

Tradeoff: O(m+n) — easy to explain and verify. Use this to establish correctness before deriving the O(log(m+n)) solution.

2. Binary search on partition (O(log min(m,n)))

Binary search on the shorter array to find the correct partition. A valid partition divides the combined array into two halves where max(left) <= min(right). The median is derived from the boundary elements.

Time
O(log min(m,n))
Space
O(1)
function findMedianSortedArrays(nums1, nums2) {
  // Ensure nums1 is the shorter array
  if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
  const m = nums1.length, n = nums2.length;
  let lo = 0, hi = m;
  while (lo <= hi) {
    const partX = Math.floor((lo + hi) / 2);
    const partY = Math.floor((m + n + 1) / 2) - partX;
    const maxLeftX = partX === 0 ? -Infinity : nums1[partX - 1];
    const minRightX = partX === m ? Infinity : nums1[partX];
    const maxLeftY = partY === 0 ? -Infinity : nums2[partY - 1];
    const minRightY = partY === n ? Infinity : nums2[partY];
    if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
      // Correct partition
      if ((m + n) % 2 === 1) return Math.max(maxLeftX, maxLeftY);
      return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
    } else if (maxLeftX > minRightY) {
      hi = partX - 1;
    } else {
      lo = partX + 1;
    }
  }
}

Tradeoff: O(log min(m,n)) — optimal. The insight: rather than merging, binary search for the partition point in the shorter array. A correct partition means the left half of the combined virtual array contains the smaller half of all elements.

Hugging Face-specific tips

This problem is notoriously hard to explain clearly. Hugging Face values clear verbal articulation: start with 'The median splits the combined array into two equal halves. I'll binary search for the partition in nums1 such that the left half of nums1 and nums2 combined equals the right half.' Then trace through one concrete example before writing code. The -Infinity/Infinity sentinels for boundary conditions are easy to forget — state them explicitly up front. Connect to ML: 'Binary search on abstract partitions is the same technique used to find the optimal threshold in a precision-recall curve.'

Common mistakes

  • Not swapping arrays to ensure binary search runs on the shorter one — if m > n, partY can go negative.
  • Forgetting -Infinity/Infinity sentinel values for the boundary cases (partX=0 or partX=m).
  • Off-by-one in partY calculation — use (m+n+1)/2 floored to handle both even and odd total lengths uniformly.
  • Not handling the edge case where one array is empty.

Follow-up questions

An interviewer at Hugging Face may pivot to one of these next:

  • Find the k-th smallest element in two sorted arrays — same binary search pattern, generalized.
  • Kth Smallest Element in a Sorted Matrix (LC 378) — binary search over value range.
  • How would you find the median of a stream of numbers as they arrive? (LC 295 — two heaps approach)

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why binary search on the shorter array?

To minimize the search space. If nums1 has m elements, the partition index ranges from 0 to m, giving O(log m) iterations. If m < n, we get O(log min(m,n)).

What does the partition represent?

partX elements from nums1 go to the left half; the rest go to the right. partY = half_total - partX elements from nums2 go to the left. A valid partition ensures max(left) <= min(right) for both arrays.

Why use (m+n+1)/2 instead of (m+n)/2 for half-total?

The +1 ensures that when the total length is odd, the left half has one more element than the right. Taking floor ensures the median is always at max(maxLeftX, maxLeftY) for odd lengths.

Practice these live with InterviewChamp.AI

Drill Median of Two Sorted Arrays and other Hugging Face interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →