Skip to main content

4. Median of Two Sorted Arrays

hardAsked at Google

Given two sorted arrays, return the median of the combined array in O(log(min(m, n))). Google asks this to test whether you can apply binary search on the smaller array's partition position — one of the hardest applications of the binary-search paradigm.

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

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Google L5+ onsite reports cite this as the algorithmic-thinking round.
  • Blind (2025-08)— Less common but recurring Google senior IC question.

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

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

Example 2

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

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

Approaches

1. Merge then index

Merge both arrays in sorted order, then index the middle.

Time
O(m + n)
Space
O(m + n)
function findMedianSortedArraysMerge(nums1, nums2) {
  const merged = [];
  let i = 0, j = 0;
  while (i < nums1.length && j < nums2.length) {
    if (nums1[i] <= nums2[j]) merged.push(nums1[i++]);
    else merged.push(nums2[j++]);
  }
  while (i < nums1.length) merged.push(nums1[i++]);
  while (j < nums2.length) merged.push(nums2[j++]);
  const n = merged.length;
  if (n % 2) return merged[n >> 1];
  return (merged[n / 2 - 1] + merged[n / 2]) / 2;
}

Tradeoff: Linear, fails the O(log) requirement. Mention to anchor.

2. Binary search on partition (optimal)

Binary search the smaller array's partition index. A valid partition has equal-ish halves with the left max of both <= right min of both.

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;
  let lo = 0, hi = m;
  while (lo <= hi) {
    const i = (lo + hi) >> 1;
    const j = ((m + n + 1) >> 1) - i;
    const left1 = i === 0 ? -Infinity : nums1[i - 1];
    const right1 = i === m ? Infinity : nums1[i];
    const left2 = j === 0 ? -Infinity : nums2[j - 1];
    const right2 = j === n ? Infinity : nums2[j];
    if (left1 <= right2 && left2 <= right1) {
      if ((m + n) % 2) return Math.max(left1, left2);
      return (Math.max(left1, left2) + Math.min(right1, right2)) / 2;
    } else if (left1 > right2) hi = i - 1;
    else lo = i + 1;
  }
  return 0;
}

Tradeoff: True O(log) by searching only the smaller array's partition. The invariant — left1 <= right2 AND left2 <= right1 — uniquely identifies the median split.

Google-specific tips

Google interviewers grade this on the invariant articulation. State out loud: 'I'm searching for a partition position i in nums1 such that the corresponding j in nums2 makes the left half and right half balanced — specifically, left1 ≤ right2 and left2 ≤ right1.' Coding this without articulating the invariant looks like memorization, not understanding.

Common mistakes

  • Forgetting to swap so nums1 is the smaller — otherwise hi can blow past valid partitions.
  • Off-by-one with j computation; +1 inside the half-length formula handles both odd and even total sizes.
  • Missing the -Infinity / +Infinity sentinels for partition at the array boundary.

Follow-up questions

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

  • Find the k-th smallest in two sorted arrays (LC 4 generalization).
  • Three sorted arrays.
  • Streams instead of 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 search the smaller array?

Binary-search bounds. If we searched the larger, we'd waste log work where the partition can't validly exist. Swapping ensures O(log min(m, n)).

Is the O(m + n) merge solution acceptable in Google interviews?

For phone screens, often yes (mention it then code it). For onsite, almost never — the problem name itself signals 'find a log solution.' Have the binary-search version ready.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →