Skip to main content

22. Median of Two Sorted Arrays

hardAsked at Revolut

Find the median of two sorted arrays in O(log(min(m,n))), a Revolut hard-screen that mirrors finding the median quote across two sorted FX-rate feeds in microseconds.

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

Problem

Given two sorted arrays nums1 and nums2 of size m and n, return the median of the two sorted arrays. The overall runtime should be O(log(min(m,n))).

Constraints

  • 0 <= m, n <= 1000
  • 1 <= m + n <= 2000
  • -10^6 <= nums[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 then index

Merge into one sorted array, return the middle element(s).

Time
O(m+n)
Space
O(m+n)
const all = [...nums1, ...nums2].sort((a,b)=>a-b);
const t = all.length;
return t%2? all[t>>1] : (all[t/2-1]+all[t/2])/2;

Tradeoff:

2. Binary search on partition

Binary search on the smaller array for a partition where left halves' max <= right halves' min. Logarithmic time on the shorter array.

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, j = half - i;
    const aL = i ? a[i-1] : -Infinity, aR = i < m ? a[i] : Infinity;
    const bL = j ? b[j-1] : -Infinity, bR = j < n ? b[j] : Infinity;
    if (aL <= bR && bL <= aR){
      if ((m + n) % 2) return Math.max(aL, bL);
      return (Math.max(aL, bL) + Math.min(aR, bR)) / 2;
    }
    if (aL > bR) hi = i - 1; else lo = i + 1;
  }
}

Tradeoff:

Revolut-specific tips

Revolut hard-screens want you to explicitly state WHY you binary-search the shorter array — they value candidates who connect log(min(m,n)) to the SLA budget on a hot FX-quote median calculation.

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

Practice these live with InterviewChamp.AI →