Skip to main content

95. Median of Two Sorted Arrays

hardAsked at Vercel

Find the median of two sorted arrays in O(log(min(m,n))). Vercel asks this for the binary-search partition technique — a hard problem that distinguishes top candidates and shows up in their per-region latency aggregation when merging metric streams.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel platform onsite; reserved for senior interviews.
  • Blind (2026-Q1)— Listed as a Vercel hard.

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, 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 = [1,2,3], median = 2.

Example 2

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

Approaches

1. Merge then find median

Merge two sorted arrays; index into the middle.

Time
O(m+n)
Space
O(m+n)
// Works but doesn't meet the log constraint.

Tradeoff: Acceptable as a warm-up to motivate the harder version.

2. Binary search partition on shorter array (optimal)

Binary search the partition point in the shorter array. For each candidate, derive the partition in the other array via half-of-total. Check the four boundary values; if not yet sorted, narrow.

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 half = Math.floor((m + n + 1) / 2);
  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 ((m + n) % 2 === 1) return Math.max(aLeft, bLeft);
      return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2;
    }
    if (aLeft > bRight) hi = i - 1;
    else lo = i + 1;
  }
}

Tradeoff: O(log(min(m,n))). The idea: partition the combined sorted array into two halves of equal size; binary search the partition point. Verbose but correct.

Vercel-specific tips

Vercel grades the binary-search partition. Bonus signal: ensuring you binary search the SHORTER array (avoids out-of-bounds on the partition formula) and using +/-Infinity for the boundary cases. This problem rewards careful articulation — talk through the partition invariant before coding.

Common mistakes

  • Binary searching the longer array — produces invalid j values.
  • Off-by-one on the half formula — must be (m+n+1)/2 (floor) to keep left half >= right half by 1 for odd lengths.
  • Forgetting +/-Infinity boundaries — crashes on i=0 or i=m.

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • Find Kth smallest in two sorted arrays — same partition technique.
  • Median of K sorted arrays — much harder.
  • Streaming median (LC 295) — different problem, two heaps.

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 (m+n+1)/2?

We want the left half to have ceil((m+n)/2) elements. For odd totals, left has one more; for even, equal. This formula achieves both.

Why search the shorter array?

j = half - i. If i is in [0, m], then j is in [half - m, half]. For j to be in [0, n], we need m <= n. Swapping ensures this.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →