Skip to main content

24. Median of Two Sorted Arrays

hardAsked at Udemy

Find the median of two sorted arrays in O(log(m+n)) — Udemy uses this to test binary search mastery applied to statistical ranking and recommendation scoring.

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

Problem

Given two sorted arrays nums1 and nums2 of size m and n, return the median of the two sorted arrays. The overall run time complexity must be O(log(m+n)).

Constraints

  • 0 <= m, n <= 1000
  • 0 <= m + n
  • nums1 and nums2 are sorted in non-decreasing order

Examples

Example 1

Input
nums1 = [1,3], nums2 = [2]
Output
2.00000

Example 2

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

Approaches

1. Merge and select

Merge both arrays then return the middle element — O(m+n) time, does not meet the log constraint.

Time
O(m+n)
Space
O(m+n)
function findMedianSortedArrays(nums1, nums2) {
  const merged = [...nums1, ...nums2].sort((a,b) => a-b);
  const mid = Math.floor(merged.length / 2);
  return merged.length % 2 === 0 ? (merged[mid-1] + merged[mid]) / 2 : merged[mid];
}

Tradeoff:

2. Binary search partition

Binary search on the smaller array to find a partition such that all elements on the left side of both partitions are <= all elements on the right side; the median is then computed from the four boundary elements.

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 = (lo + hi) >> 1;
    const j = ((m + n + 1) >> 1) - i;
    const maxL1 = i === 0 ? -Infinity : nums1[i-1];
    const minR1 = i === m ? Infinity : nums1[i];
    const maxL2 = j === 0 ? -Infinity : nums2[j-1];
    const minR2 = j === n ? Infinity : nums2[j];
    if (maxL1 <= minR2 && maxL2 <= minR1) {
      const left = Math.max(maxL1, maxL2);
      if ((m + n) % 2 === 1) return left;
      return (left + Math.min(minR1, minR2)) / 2;
    } else if (maxL1 > minR2) hi = i - 1;
    else lo = i + 1;
  }
}

Tradeoff:

Udemy-specific tips

Udemy asks about e-learning recommendation systems, content search, and marketplace algorithms — balanced mix of arrays, hash maps, and dynamic programming problems.

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

Practice these live with InterviewChamp.AI →