Skip to main content

4. Median of Two Sorted Arrays

hardAsked at AMD

Find the median of two sorted arrays in O(log(m+n)). AMD asks this as the canonical binary-search-on-two-arrays hard — the O(log n) constraint forces a partitioning insight rather than a merge. AMD engineers apply similar binary-search-based reasoning to bisecting performance bottlenecks in multi-stream profiler data.

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

Source citations

Public interview reports confirming this problem appears in AMD loops.

  • Glassdoor (2025-12)— AMD SWE hard-round reports include Median of Two Sorted Arrays as a signal problem for candidates applying to performance-critical roles.
  • Blind (2025-08)— AMD interview threads note this as an infrequent but high-signal hard that differentiates strong candidates in final rounds.

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

Explanation: Merged array is [1,2,3]. Median is 2.

Example 2

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

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

Approaches

1. O(log(min(m,n))) binary search on partition

Binary search on the smaller array to find a partition point. The partition must satisfy: all elements on the left of the combined partition <= all elements on the right. The median is derived from the 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 partX = (lo + hi) >> 1;
    const partY = ((m + n + 1) >> 1) - partX;
    const maxLeftX = partX === 0 ? -Infinity : nums1[partX - 1];
    const minRightX = partX === m ? Infinity : nums1[partX];
    const maxLeftY = partY === 0 ? -Infinity : nums2[partY - 1];
    const minRightY = partY === n ? Infinity : nums2[partY];
    if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
      if ((m + n) % 2 === 0) {
        return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
      }
      return Math.max(maxLeftX, maxLeftY);
    } else if (maxLeftX > minRightY) {
      hi = partX - 1;
    } else {
      lo = partX + 1;
    }
  }
  return 0;
}

Tradeoff: O(log(min(m,n))) — strictly better than O(log(m+n)) since we binary search only the smaller array. O(1) space. The partition-validity condition is the key insight: the left half of the combined sorted array must contain (m+n+1)/2 elements.

AMD-specific tips

This problem is about the invariant: the partition divides all 2*(m+n) positions into two halves of equal size, and every element in the left half is <= every element in the right half. Walk through the invariant setup before writing any code — AMD interviewers reward structured thinking. Use -Infinity and +Infinity as sentinels for edge partitions (partX=0 or partX=m) to avoid branchy null checks. Always binary search the shorter array to keep the complexity O(log(min(m,n))).

Common mistakes

  • Binary searching the longer array — increases complexity unnecessarily and risks out-of-bounds partY.
  • Using (m + n) / 2 instead of (m + n + 1) / 2 for the half-size — the +1 handles the odd-length case by giving one extra element to the left half.
  • Forgetting the ±Infinity sentinel for edge partitions — leads to incorrect maxLeft/minRight at boundaries.
  • Returning max(maxLeftX, maxLeftY) for even-length arrays — correct for odd; for even you need (max of left + min of right) / 2.

Follow-up questions

An interviewer at AMD may pivot to one of these next:

  • Kth Smallest Element in Two Sorted Arrays — generalize to any k, not just the median.
  • What if you have k sorted arrays? (Extend to a heap-based approach.)
  • How would you compute the median of a streaming data set using two heaps?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why add 1 in (m+n+1)/2?

For odd total length, the median is the middle element. The +1 ensures the left half gets the extra element. For even lengths, the division rounds the same way as without +1, so it doesn't hurt.

Why binary search on the smaller array?

partY = ((m+n+1)/2) - partX. If nums1 is longer, partY could go negative (invalid). By always making nums1 the shorter array, partY is guaranteed to be in [0, n].

Practice these live with InterviewChamp.AI

Drill Median of Two Sorted Arrays and other AMD interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →