Skip to main content

32. Median of Two Sorted Arrays

hardAsked at Doordash

Find the median of two sorted arrays in O(log(m+n)) — Doordash uses binary-search-on-sorted-partition thinking in their real-time delivery ETA percentile calculations that must run in microseconds across millions of rows.

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

Problem

Given two sorted arrays nums1 and nums2 of sizes 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 <= 1000; 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -10^6 <= nums1[i], nums2[i] <= 10^6
  • Both arrays are sorted in non-decreasing order

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 = 2.5.

Approaches

1. Merge then find median

Merge both sorted arrays into one sorted array; return the middle element (or average of two middles for even total length).

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

Tradeoff:

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

Binary search for the correct partition point in the smaller array such that all left-side elements across both arrays are <= all right-side elements. Median is computed from the 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 i = Math.floor((lo + hi) / 2);
    const j = Math.floor((m + n + 1) / 2) - i;
    const maxLeft1 = i === 0 ? -Infinity : nums1[i - 1];
    const minRight1 = i === m ? Infinity : nums1[i];
    const maxLeft2 = j === 0 ? -Infinity : nums2[j - 1];
    const minRight2 = j === n ? Infinity : nums2[j];
    if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
      const maxLeft = Math.max(maxLeft1, maxLeft2);
      const minRight = Math.min(minRight1, minRight2);
      if ((m + n) % 2 === 1) return maxLeft;
      return (maxLeft + minRight) / 2;
    } else if (maxLeft1 > minRight2) {
      hi = i - 1;
    } else {
      lo = i + 1;
    }
  }
}

Tradeoff:

Doordash-specific tips

Doordash surfaces this at senior/staff levels when they want to probe binary search mastery beyond textbook examples. The key statement they want to hear: 'I'm binary-searching for the partition index in the smaller array such that the combined left halves and right halves maintain the sorted-merge invariant.' Spend the first 3 minutes walking through the partition logic on the whiteboard — don't jump to code. Common pitfalls to call out: off-by-one on the partition sizes for odd vs even total length, and forgetting to use the smaller array as nums1. Follow-up: extend to k sorted arrays.

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

Practice these live with InterviewChamp.AI →