Skip to main content

23. Median of Two Sorted Arrays

hardAsked at Figma

Find the median of the union of two sorted arrays in O(log(min(m,n))). Figma uses this to push hard-bar candidates into binary-search-on-answer territory, the same shape used for partition lookups in multiplayer cursor state.

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

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(min(m, n))).

Constraints

  • nums1.length == m, nums2.length == n
  • 0 <= m, 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.0

Example 2

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

Approaches

1. Merge then index

Merge the two sorted arrays and pick the middle element(s).

Time
O(m + n)
Space
O(m + n)
function findMedianSortedArrays(a, b) {
  const merged = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) merged.push(a[i] <= b[j] ? a[i++] : b[j++]);
  while (i < a.length) merged.push(a[i++]);
  while (j < b.length) merged.push(b[j++]);
  const n = merged.length;
  return n % 2 ? merged[n >> 1] : (merged[n / 2 - 1] + merged[n / 2]) / 2;
}

Tradeoff:

2. Binary-search partition

Binary-search a cut point on the shorter array such that the combined left half holds exactly (m+n+1)/2 elements and every left value <= every right value. Logarithmic, no merge, no extra space.

Time
O(log(min(m,n)))
Space
O(1)
function findMedianSortedArrays(a, b) {
  if (a.length > b.length) [a, b] = [b, a];
  const m = a.length, n = b.length;
  const total = m + n, half = (total + 1) >> 1;
  let lo = 0, hi = m;
  while (lo <= hi) {
    const i = (lo + hi) >> 1;
    const j = half - i;
    const aLeft = i === 0 ? -Infinity : a[i - 1];
    const aRight = i === m ? Infinity : a[i];
    const bLeft = j === 0 ? -Infinity : b[j - 1];
    const bRight = j === n ? Infinity : b[j];
    if (aLeft <= bRight && bLeft <= aRight) {
      if (total % 2) return Math.max(aLeft, bLeft);
      return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2;
    } else if (aLeft > bRight) hi = i - 1;
    else lo = i + 1;
  }
}

Tradeoff:

Figma-specific tips

Figma's hard-bar grade is whether you can derive the partition invariant on the whiteboard rather than reciting it — narrate the 'left half size' invariant before you index any array.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →