Skip to main content

22. Median of Two Sorted Arrays

hardAsked at Brex

Find the median of two sorted arrays in O(log(m+n)) — a binary search on partition problem that Brex uses to assess candidates' ability to handle ordered financial data sets efficiently.

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 must 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.00000

Example 2

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

Approaches

1. Merge then find median

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

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

Tradeoff:

2. Binary search on partition

Binary search on the smaller array to find a partition such that every element on the left of both arrays is <= every element on the right. Achieves O(log(min(m,n))).

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, half = (m + n + 1) >> 1;
  let lo = 0, hi = m;
  while (lo <= hi) {
    const i = (lo + hi) >> 1, j = half - i;
    if (i < m && B[j-1] > A[i]) lo = i + 1;
    else if (i > 0 && A[i-1] > B[j]) hi = i - 1;
    else {
      const maxL = Math.max(i>0 ? A[i-1] : -Infinity, j>0 ? B[j-1] : -Infinity);
      if ((m+n) % 2) return maxL;
      const minR = Math.min(i<m ? A[i] : Infinity, j<n ? B[j] : Infinity);
      return (maxL + minR) / 2;
    }
  }
}

Tradeoff:

Brex-specific tips

Brex asks about fintech infrastructure, multi-currency handling, and spend management algorithms. Expect LeetCode-style DSA focused on hash maps, sorting, and dynamic programming.

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

Practice these live with InterviewChamp.AI →