Skip to main content

21. Median of Two Sorted Arrays

hardAsked at Autodesk

Find the median of two sorted arrays in logarithmic time.

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 algorithm must run in O(log(min(m, n))) time.

Constraints

  • 0 <= m, n <= 1000
  • 1 <= m + n <= 2000
  • -10^6 <= nums[i] <= 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 then index

Merge the two sorted arrays and pick the middle element(s).

Time
O(m+n)
Space
O(m+n)
const merged=[]; let i=0,j=0;
while(i<m||j<n){ /* push smaller */ }
return average of middle elements;

Tradeoff:

2. Binary search partition

Binary search over the smaller array to find a partition such that left halves have (m+n+1)/2 elements and the rightmost-left of one side is <= leftmost-right of the other.

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;
  let lo = 0, hi = m;
  const half = (m + n + 1) >> 1;
  while (lo <= hi) {
    const i = (lo + hi) >> 1;
    const j = half - i;
    const Al = i === 0 ? -Infinity : A[i-1];
    const Ar = i === m ? Infinity : A[i];
    const Bl = j === 0 ? -Infinity : B[j-1];
    const Br = j === n ? Infinity : B[j];
    if (Al <= Br && Bl <= Ar) {
      if ((m + n) % 2) return Math.max(Al, Bl);
      return (Math.max(Al, Bl) + Math.min(Ar, Br)) / 2;
    } else if (Al > Br) hi = i - 1; else lo = i + 1;
  }
}

Tradeoff:

Autodesk-specific tips

Binary search on partitions mirrors Autodesk's median-finding inside BVH split heuristics for SAH (surface area heuristic) builds.

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

Practice these live with InterviewChamp.AI →