Skip to main content

81. Median of Two Sorted Arrays

hardAsked at Plaid

Find the median of two sorted arrays in O(log(min(m,n))). Plaid asks this as a binary-search-on-partitions problem because computing percentile across two sharded ledgers without merging them is the same primitive.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE III onsite — sharded-ledger percentile.
  • LeetCode Discuss (2026)— Plaid hard binary-search.

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, 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.0

Example 2

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

Approaches

1. Merge and pick median

Merge both arrays; pick the middle.

Time
O(m+n)
Space
O(m+n)
// Misses the log bound.

Tradeoff: Linear — misses the requirement.

2. Binary search on partition

Partition nums1 at i, then n2 partition j = (m+n+1)/2 - i. Valid partition: max(left halves) <= min(right halves). Adjust i via binary search.

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;
  while (lo <= hi) {
    const i = (lo + hi) >> 1;
    const j = ((m + n + 1) >> 1) - 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 === 0) return (Math.max(aL, bL) + Math.min(aR, bR)) / 2;
      return Math.max(aL, bL);
    }
    if (aL > bR) hi = i - 1;
    else lo = i + 1;
  }
}

Tradeoff: Logarithmic in the smaller array. The two-partition idea is the crucial insight.

Plaid-specific tips

Plaid grades this on whether you can articulate the partition condition. Bonus signal: ensure you binary-search the smaller array (swap if needed) for the tightest log bound. Connect to sharded-ledger percentile queries where you can't afford to merge across shards.

Common mistakes

  • Off-by-one on j = (m+n+1)/2 - i — verify with small examples.
  • Mis-handling the empty-side sentinels (-Infinity, Infinity).
  • Binary-searching the larger array — works but worse log bound.

Follow-up questions

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

  • Kth smallest of two sorted arrays.
  • Sliding median across two streams.
  • Median of multiple sorted arrays — generalize via heap.

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 is j = (m+n+1)/2 - i?

We want the combined left half to have exactly (m+n+1)/2 elements. Since i are from a, j must be the remainder from b.

Why search the smaller array?

To bound i in [0, m] tightly. If we searched the larger, j could go negative and require extra handling.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →