Skip to main content

24. Median of Two Sorted Arrays

hardAsked at Chegg

Find the median of two sorted arrays in O(log(m+n)) — a binary search hard that Chegg uses to test whether candidates can handle partitioned sorted data as arises in distributed search indexing.

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 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

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 find median

Merge both arrays into a sorted array, then pick the middle — O(m+n) time, O(m+n) space, misses the log requirement.

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)
    merged.push(nums1[i] <= nums2[j] ? nums1[i++] : nums2[j++]);
  while (i < nums1.length) merged.push(nums1[i++]);
  while (j < nums2.length) merged.push(nums2[j++]);
  const n = merged.length;
  return n % 2 ? merged[Math.floor(n/2)] : (merged[n/2-1] + merged[n/2]) / 2;
}

Tradeoff:

2. Binary search on partition

Binary search on the smaller array to find the correct partition such that all left elements are less than all right elements across both arrays; compute median 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 i = Math.floor((lo + hi) / 2);
    const j = Math.floor((m + n + 1) / 2) - i;
    const lMax1 = i === 0 ? -Infinity : nums1[i-1];
    const rMin1 = i === m ? Infinity : nums1[i];
    const lMax2 = j === 0 ? -Infinity : nums2[j-1];
    const rMin2 = j === n ? Infinity : nums2[j];
    if (lMax1 <= rMin2 && lMax2 <= rMin1) {
      const leftMax = Math.max(lMax1, lMax2);
      const rightMin = Math.min(rMin1, rMin2);
      return (m + n) % 2 ? leftMax : (leftMax + rightMin) / 2;
    } else if (lMax1 > rMin2) hi = i - 1;
    else lo = i + 1;
  }
}

Tradeoff:

Chegg-specific tips

Chegg occasionally surfaces this in senior-level rounds — walk through the partition invariant with concrete numbers on a whiteboard; the Infinity sentinel values for empty partitions are a detail they probe.

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

Practice these live with InterviewChamp.AI →