Skip to main content

4. Median of Two Sorted Arrays

hardAsked at Uber

Given two sorted arrays nums1 and nums2, return the median of the combined sorted array in O(log(min(m, n))). Uber asks this to test whether you can narrow from O(m+n) merge to a binary-search partition argument.

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

Source citations

Public interview reports confirming this problem appears in Uber loops.

  • Glassdoor (2026-Q1)— Uber senior onsite reports include this as a 45-minute hard.
  • Blind (2025-10)— Recurring in Uber L5+ algorithm-track interviews.

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 is 2.

Example 2

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

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

Approaches

1. Merge then pick (linear)

Merge the two arrays in O(m+n) and index into the median position(s).

Time
O(m + n)
Space
O(m + n)
function findMedianSortedArraysMerge(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) >> 1] : (merged[n / 2 - 1] + merged[n / 2]) / 2;
}

Tradeoff: Easy and correct but misses the O(log) requirement. Always state this exists before showing the binary search.

2. Binary search on partition (optimal)

Binary-search a cut position in the shorter array. The matching cut in the longer array makes the two left halves of total size (m+n+1)/2. Check max-left <= min-right invariant.

Time
O(log(min(m, n)))
Space
O(1)
function findMedianSortedArrays(nums1, nums2) {
  if (nums1.length > nums2.length) [nums1, nums2] = [nums2, nums1];
  const m = nums1.length, n = nums2.length;
  let lo = 0, hi = m;
  const half = (m + n + 1) >> 1;
  while (lo <= hi) {
    const i = (lo + hi) >> 1;
    const j = half - i;
    const left1 = i === 0 ? -Infinity : nums1[i - 1];
    const right1 = i === m ? Infinity : nums1[i];
    const left2 = j === 0 ? -Infinity : nums2[j - 1];
    const right2 = j === n ? Infinity : nums2[j];
    if (left1 <= right2 && left2 <= right1) {
      if ((m + n) % 2) return Math.max(left1, left2);
      return (Math.max(left1, left2) + Math.min(right1, right2)) / 2;
    } else if (left1 > right2) {
      hi = i - 1;
    } else {
      lo = i + 1;
    }
  }
  return 0;
}

Tradeoff: True O(log) without merging. The invariant max-left <= min-right is what's being binary-searched. Always binary-search the shorter array so hi stays bounded by min(m, n).

Uber-specific tips

Uber's bar on this one is whether you can state the partition invariant clearly. Say: 'I'm choosing a cut in nums1 — that determines the matching cut in nums2 because together they must total (m+n+1)/2 elements on the left. The cut is correct when the left side's max <= the right side's min on the other array.' Without that narration, even working code lands short of the bar.

Common mistakes

  • Binary-searching the longer array — makes the partition arithmetic harder and the bound looser.
  • Forgetting the +/-Infinity sentinels when a cut is at the boundary.
  • Off-by-one on the half-length when m+n is odd vs even.

Follow-up questions

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

  • K-th element of two sorted arrays — same partition idea, target k instead of (m+n)/2.
  • What if the arrays were streaming and you needed a running median? (Two heaps — see LC 295.)
  • What if you had K sorted arrays? (Generalize via heap + index.)

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 the shorter array?

It bounds hi to min(m, n), giving log(min(m, n)) which is asymptotically optimal. If you binary-searched the longer one, the implicit cut in the shorter could go out of bounds.

Is the merge solution ever acceptable?

Only as a stepping stone. The problem statement explicitly demands O(log(m+n)). Uber's bar is the O(log) partition; merge alone is a partial-credit answer.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →