Skip to main content

24. Median of Two Sorted Arrays

hardAsked at Monzo

Combine two sorted ledger snapshots and return the median transaction amount in O(log) time.

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, n <= 1000
  • 1 <= m + n <= 2000

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

Merge both sorted arrays into one and pick the middle element(s).

Time
O(m+n)
Space
O(m+n)
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 t = merged.length;
return t % 2 ? merged[(t-1)/2] : (merged[t/2 - 1] + merged[t/2]) / 2;

Tradeoff:

2. Binary search the smaller array

Partition the shorter array; binary search for the partition where the left halves of both arrays together are exactly half of the combined elements and the boundary values satisfy the median condition.

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

Tradeoff:

Monzo-specific tips

Monzo asks this for the log-time defense; tie it to how ledger snapshots are already sorted on the storage side.

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

Practice these live with InterviewChamp.AI →