Skip to main content

4. Median of Two Sorted Arrays

hardAsked at Broadcom

Find the median of two sorted arrays in O(log(m+n)) time. Broadcom asks this because binary search on implicit data structures is a core skill for their systems engineers — the same partition-finding logic appears in percentile computation for network latency telemetry and SLA threshold analysis.

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

Source citations

Public interview reports confirming this problem appears in Broadcom loops.

  • Glassdoor (2025-10)— Cited in Broadcom senior SWE onsite reports as a binary-search-on-arrays problem reserved for principal-level interviews.
  • Blind (2025-08)— Broadcom threads mention Median of Two Sorted Arrays as a hard problem that separates strong from average candidates.

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

Explanation: Merged array = [1,2,3]. Median = 2.

Example 2

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

Explanation: Merged array = [1,2,3,4]. Median = (2+3)/2 = 2.5.

Approaches

1. Merge and find median (O(m+n))

Merge both arrays and return the middle element (or average of two middle elements). Simple but doesn't meet the O(log) requirement.

Time
O(m + n)
Space
O(m + n)
function findMedianSortedArrays(nums1, nums2) {
  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 mid = Math.floor(merged.length / 2);
  return merged.length % 2 === 0 ? (merged[mid - 1] + merged[mid]) / 2 : merged[mid];
}

Tradeoff: O(m+n) — correct but does not satisfy the problem's O(log(m+n)) requirement. Mention as the baseline.

2. Binary search on partition (O(log min(m,n)))

Binary search on the shorter array to find a partition point. The partition divides both arrays such that every element on the left half is ≤ every element on the right half. The median is derived from the partition boundary values.

Time
O(log min(m, n))
Space
O(1)
function findMedianSortedArrays(nums1, nums2) {
  // Ensure nums1 is the shorter array
  if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
  const m = nums1.length, n = nums2.length;
  let lo = 0, hi = m;
  while (lo <= hi) {
    const px = Math.floor((lo + hi) / 2); // partition in nums1
    const py = Math.floor((m + n + 1) / 2) - px; // partition in nums2
    const maxLeftX  = px === 0 ? -Infinity : nums1[px - 1];
    const minRightX = px === m ?  Infinity : nums1[px];
    const maxLeftY  = py === 0 ? -Infinity : nums2[py - 1];
    const minRightY = py === n ?  Infinity : nums2[py];
    if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
      if ((m + n) % 2 === 0) return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
      return Math.max(maxLeftX, maxLeftY);
    } else if (maxLeftX > minRightY) {
      hi = px - 1;
    } else {
      lo = px + 1;
    }
  }
  return -1; // unreachable
}

Tradeoff: O(log min(m,n)) time, O(1) space. This is the canonical hard answer. The key insight: finding the correct partition is equivalent to finding the median. Requires careful boundary handling (Infinity for out-of-bounds edges).

Broadcom-specific tips

At Broadcom, state the core insight before coding: 'I'm not searching for a value — I'm searching for a partition point that correctly splits both arrays into equal halves.' Walk through the partition invariant: maxLeft ≤ minRight on both sides simultaneously. Use -Infinity and Infinity as sentinel boundary values. Broadcom interviewers for senior roles expect you to derive the total partition size: py = (m+n+1)/2 - px and explain why the +1 handles odd-length combined arrays.

Common mistakes

  • Swapping the arrays without re-entering the function — always binary search on the shorter array to ensure py stays non-negative.
  • Wrong sentinel values for boundary partitions — use ±Infinity, not 0 or -1.
  • Off-by-one in the total-half formula — (m+n+1)/2 ensures the left half gets the extra element when total length is odd.
  • Not handling the edge case where one array is fully on one side of the partition (px=0 or px=m).

Follow-up questions

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

  • Kth smallest element in two sorted arrays (generalisation of this problem).
  • Kth smallest element in a sorted matrix (LC 378).
  • How would you find the median of k sorted arrays efficiently?

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

The partition in nums2 is determined by the partition in nums1: py = half - px. To keep py in bounds [0, n], px must be in [half-n, half]. Binary searching on the shorter array guarantees the invariant holds without additional clamping.

What does the partition invariant guarantee?

Every element in the combined left half is ≤ every element in the combined right half. When maxLeftX ≤ minRightY and maxLeftY ≤ minRightX, the partition is correct and the median can be read directly from the boundary values.

How is the median computed from the partition?

For even total length: (max of left boundaries + min of right boundaries) / 2. For odd total length: max of left boundaries (since the left half has one extra element).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →