Skip to main content

22. Median of Two Sorted Arrays

hardAsked at Freshworks

Find the median across two sorted arrays in O(log min(m, n)) — Freshworks asks this to probe binary-search fluency over a partitioned domain.

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

Problem

Given two sorted arrays nums1 and nums2 of sizes m and n, return the median of the two sorted arrays. The runtime must be O(log(min(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.0

Example 2

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

Approaches

1. Brute force (merge then index)

Merge both arrays in O(m+n) and pick the middle index/indices.

Time
O(m+n)
Space
O(m+n)
const merged = [];
let i=0,j=0;
while(i<nums1.length||j<nums2.length){ /* push smaller */ }
const mid=(merged.length-1)/2;
return (merged[Math.floor(mid)] + merged[Math.ceil(mid)]) / 2;

Tradeoff:

2. Binary search on smaller array's partition

Pick the smaller array. Binary search a partition i in [0, m]. Compute j = (m + n + 1) / 2 - i. Check four boundary values; tighten the search until left_max <= right_min on both sides.

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:

Freshworks-specific tips

Freshworks scores hard on whether you binary-search the SMALLER array — say that out loud before coding because that's where the log min(m, n) bound comes from.

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

Practice these live with InterviewChamp.AI →