Skip to main content

93. Median of Two Sorted Arrays

hardAsked at Workday

Find the median of two sorted arrays in O(log min(m, n)). Workday uses this for binary-search-on-partition mastery — the hardest of their binary-search variants.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2026-Q1)— Workday SDE3 onsite.

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 pick

Merge both arrays; return middle element(s).

Time
O(m + n)
Space
O(m + n)
// works but O(m+n) — fails the O(log) requirement

Tradeoff: Linear, not log.

2. Binary search on partition

Binary search the smaller array for a partition such that combined left half == combined right half (in size) AND max(left) <= min(right).

Time
O(log min(m, n))
Space
O(1)
function findMedianSortedArrays(a, b) {
  if (a.length > b.length) return findMedianSortedArrays(b, a);
  const m = a.length, n = b.length;
  const total = m + n;
  const half = (total + 1) >> 1;
  let lo = 0, hi = m;
  while (lo <= hi) {
    const i = (lo + hi) >> 1;
    const j = half - i;
    const aLeft = i === 0 ? -Infinity : a[i - 1];
    const aRight = i === m ? Infinity : a[i];
    const bLeft = j === 0 ? -Infinity : b[j - 1];
    const bRight = j === n ? Infinity : b[j];
    if (aLeft <= bRight && bLeft <= aRight) {
      if (total % 2 === 1) return Math.max(aLeft, bLeft);
      return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2;
    }
    if (aLeft > bRight) hi = i - 1;
    else lo = i + 1;
  }
  return -1;
}

Tradeoff: Binary-search the partition of the SHORTER array. The other partition is determined by total size. Median lives at the partition boundary.

Workday-specific tips

Workday wants the partition approach. State 'binary search the shorter array' explicitly. The sentinel ±Infinity for boundaries eliminates edge cases. This is hard — be very deliberate.

Common mistakes

  • Searching the longer array — wastes log work.
  • Off-by-one with half = (total + 1) >> 1 — must round up for odd total.
  • Forgetting ±Infinity sentinels — boundary cases crash.

Follow-up questions

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

  • Kth Smallest Element in Two Sorted Arrays.
  • Sliding Window Median (LC 480).
  • If you can't binary-search the partition, what's plan B?

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

Median splits the combined array into two halves of equal size. Find the partition where left-half max <= right-half min.

Why search shorter?

log of the shorter array is the lower bound. Plus, the partition index in the shorter array is bounded — the longer array fills the rest.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →