Skip to main content

24. Median of Two Sorted Arrays

hardAsked at Coupang

Find the median of two sorted arrays in O(log) time, mirroring how Coupang's same-day delivery routing computes the median dispatch time across two pre-sorted regional batches without merging them.

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

Problem

Given two sorted arrays nums1 and nums2 of sizes m and n, return the median of the combined sorted array. Solve in O(log (m+n)).

Constraints

  • 0 <= m, n <= 1000
  • 1 <= m + n <= 2000
  • -10^6 <= nums1[i], nums2[j] <= 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 and find middle

Merge into a single sorted array, then return the middle.

Time
O(m+n)
Space
O(m+n)
const merged = [...nums1, ...nums2].sort((a, b) => a - b);
const n = merged.length;
return n % 2 ? merged[n>>1] : (merged[n/2-1] + merged[n/2]) / 2;

Tradeoff:

2. Binary search on shorter array

Partition the shorter array; binary-search the partition that splits both arrays into equal-size halves with left max <= right min on both sides.

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, half = (m + n + 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 ((m + n) % 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:

Coupang-specific tips

Coupang's same-day delivery routing computes median dispatch time across pre-sorted regional batches without merging; log-time partition binary search is the canonical pattern for SLA-bounded merge-free statistics.

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 Coupang interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →