Skip to main content

4. Median of Two Sorted Arrays

hardAsked at eBay

eBay's pricing analytics team computes median transaction prices across two buyer segments in real time — combining sorted bid histories without merging them. Median of Two Sorted Arrays is the flagship O(log(m+n)) algorithm that eBay uses at the senior level to test binary search mastery beyond basic forms. The partition-based approach is notoriously tricky and strongly differentiates senior candidates.

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

Source citations

Public interview reports confirming this problem appears in eBay loops.

  • Glassdoor (2025-11)— Reported as an occasional eBay hard problem for senior/staff SWE candidates; rarely asked at junior level.
  • Blind (2025-09)— eBay SWE threads note Median of Two Sorted Arrays as a signal problem for senior algorithm competency.

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: [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 (O(m+n))

Merge both arrays into a single sorted array and return the middle element (or average of two middle elements 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 total = merged.length;
  const mid = Math.floor(total / 2);
  return total % 2 === 0 ? (merged[mid - 1] + merged[mid]) / 2 : merged[mid];
}

Tradeoff: O(m+n) time and space — correct but does not meet the O(log(m+n)) requirement. State this approach first, then pivot to the binary search solution.

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

Binary search on the smaller array to find a partition point. Ensure the partition divides both arrays such that every element on the left side is <= every element on the right side. The median is then at the partition boundary.

Time
O(log(min(m, n)))
Space
O(1)
function findMedianSortedArrays(nums1, nums2) {
  // Ensure nums1 is the smaller array
  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 = Math.floor((lo + hi) / 2);
    const partY = Math.floor((m + n + 1) / 2) - 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) {
      // Correct partition found
      const maxLeft = Math.max(maxLeftX, maxLeftY);
      if ((m + n) % 2 === 1) return maxLeft;
      return (maxLeft + Math.min(minRightX, minRightY)) / 2;
    } else if (maxLeftX > minRightY) {
      hi = partX - 1; // move left in nums1
    } else {
      lo = partX + 1; // move right in nums1
    }
  }
  return 0; // unreachable given valid input
}

Tradeoff: O(log(min(m,n))) time, O(1) space — meets the problem's requirement. Conceptually: 'find the cut that puts the smallest (m+n)/2 elements on the left of both arrays combined.' The -Infinity/Infinity sentinels handle edge cases when a partition is at the array boundary.

eBay-specific tips

For eBay senior interviews, start with the O(m+n) merge approach and explicitly say: 'This is O(m+n) — the problem requires O(log(m+n)), so let me think about binary search.' Then describe the partition insight verbally before coding: 'I want to find a cut in nums1 such that all elements left of both cuts are <= all elements right of both cuts.' The -Infinity and Infinity sentinels for boundary partitions are critical to state upfront. Expect to spend 25+ minutes on this problem.

Common mistakes

  • Not swapping to ensure the smaller array is binary-searched — always search the smaller array to keep hi = m bounded.
  • Off-by-one in partY calculation — partY = floor((m+n+1)/2) - partX works for both odd and even totals (the +1 biases toward the left for odd totals).
  • Forgetting the -Infinity/Infinity sentinels — when partX = 0 or partX = m, one side of the partition is empty and needs a sentinel.
  • Returning the average for odd total length — for odd (m+n), the median is max(maxLeftX, maxLeftY) without averaging.

Follow-up questions

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

  • Kth Smallest Element in Two Sorted Arrays — generalization of finding the kth element, which this problem reduces to.
  • How would you find the median of k sorted arrays efficiently?
  • Can you solve this problem for three sorted arrays? What is the time complexity?

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 binary search on the smaller array?

To minimize the search range and avoid out-of-bounds partY values. If m <= n, then 0 <= partX <= m guarantees 0 <= partY <= n always.

What does the correct partition guarantee?

maxLeftX <= minRightY AND maxLeftY <= minRightX means every element in the combined left partition is <= every element in the combined right partition. The median lives at this boundary.

Why is partY = floor((m+n+1)/2) - partX?

The combined left partition has floor((m+n+1)/2) elements. partY elements come from nums2 and partX come from nums1. The +1 ensures that for odd totals, the left half has one more element — making max(maxLeftX, maxLeftY) the median without averaging.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →