Skip to main content

4. Median of Two Sorted Arrays

hardAsked at Airbnb

Find the exact midpoint of two sorted price lists without merging them — Airbnb's dynamic pricing engine computes real-time median nightly rates across two independently sorted market segments to anchor smart pricing recommendations for hosts.

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 must 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 = 2.

Example 2

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

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

Approaches

1. Merge and find median

Merge the two sorted arrays into one sorted array in O(m+n), then return the middle element. Easy to implement but violates the O(log(m+n)) constraint.

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);
  if (merged.length % 2 === 1) return merged[mid];
  return (merged[mid - 1] + merged[mid]) / 2;
}

Tradeoff:

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

Binary search on the smaller array for a partition point. Find partitions in both arrays such that the left halves max <= right halves min. The median is derived from the four boundary values.

Time
O(log(min(m,n)))
Space
O(1)
function findMedianSortedArrays(nums1, nums2) {
  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 partA = (lo + hi) >> 1;
    const partB = ((m + n + 1) >> 1) - partA;
    const maxLeftA = partA === 0 ? -Infinity : nums1[partA - 1];
    const minRightA = partA === m ? Infinity : nums1[partA];
    const maxLeftB = partB === 0 ? -Infinity : nums2[partB - 1];
    const minRightB = partB === n ? Infinity : nums2[partB];
    if (maxLeftA <= minRightB && maxLeftB <= minRightA) {
      if ((m + n) % 2 === 1) return Math.max(maxLeftA, maxLeftB);
      return (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2;
    } else if (maxLeftA > minRightB) {
      hi = partA - 1;
    } else {
      lo = partA + 1;
    }
  }
}

Tradeoff:

Airbnb-specific tips

This is one of Airbnb's signature hard problems. State the O(log(m+n)) requirement yourself before being asked — it signals you know the intended approach. The key invariant to explain: 'I am searching for the correct partition such that everything on the left side is smaller than everything on the right side across both arrays.' Draw a two-row partition diagram. Use -Infinity and +Infinity as sentinels for empty halves — this eliminates edge-case conditionals and keeps the code clean.

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

Practice these live with InterviewChamp.AI →