Skip to main content

88. Median of Two Sorted Arrays

hardAsked at Reddit

Find the median of two sorted arrays in O(log(min(m, n))). Reddit uses this to test binary-search-over-partitions — relevant when merging sorted vote-tally arrays from two shards to find a percentile cutoff.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit infra-team 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 <= 1000
  • 0 <= 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 two sorted arrays; return middle element(s).

Time
O(m + n)
Space
O(m + n)
function findMedianSortedArrays(nums1, nums2) {
  const merged = [...nums1, ...nums2].sort((a, b) => a - b);
  const k = merged.length;
  if (k % 2) return merged[Math.floor(k / 2)];
  return (merged[k / 2 - 1] + merged[k / 2]) / 2;
}

Tradeoff: Linear time but fails the O(log(m+n)) requirement.

2. Binary search on partition (optimal)

Partition nums1 at i and nums2 at j = (m+n+1)/2 - i. Check that nums1[i-1] <= nums2[j] and nums2[j-1] <= nums1[i]. Adjust i via binary search.

Time
O(log(min(m, n)))
Space
O(1)
function findMedianSortedArrays(nums1, nums2) {
  if (nums1.length > nums2.length) [nums1, nums2] = [nums2, nums1];
  const m = nums1.length, n = nums2.length, half = (m + n + 1) >> 1;
  let lo = 0, hi = m;
  while (lo <= hi) {
    const i = (lo + hi) >> 1;
    const j = half - i;
    const l1 = i === 0 ? -Infinity : nums1[i - 1];
    const r1 = i === m ? Infinity : nums1[i];
    const l2 = j === 0 ? -Infinity : nums2[j - 1];
    const r2 = j === n ? Infinity : nums2[j];
    if (l1 <= r2 && l2 <= r1) {
      if ((m + n) % 2) return Math.max(l1, l2);
      return (Math.max(l1, l2) + Math.min(r1, r2)) / 2;
    }
    if (l1 > r2) hi = i - 1;
    else lo = i + 1;
  }
}

Tradeoff: Logarithmic. The hardest binary search on LC.

Reddit-specific tips

Reddit interviewers know this is a notoriously tricky problem. Bonus signal: walk through the invariants (left half size = (m+n+1)/2, l1 <= r2, l2 <= r1) before coding. Sign of senior engineering: explicit verification of edge cases.

Common mistakes

  • Forgetting to make nums1 the shorter array (essential to bound the binary search).
  • Off-by-one on half = (m+n+1)/2 (handles odd total).
  • Using Infinity inconsistently between sentinels.

Follow-up questions

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

  • Find median in a data stream (LC 295).
  • Sliding window median (LC 480).
  • Kth smallest of two sorted arrays.

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 binary-search the shorter array?

The search range is [0, min(m,n)], so picking the shorter gives faster runtime and easier bounds.

Why does the invariant hold?

l1 <= r2 and l2 <= r1 mean the left halves contain only values ≤ the right halves of either array. Median is at the boundary.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →