Skip to main content

4. Median of Two Sorted Arrays

hardAsked at Linear

Find the median of two sorted arrays in O(log(m+n)). Linear asks this to see if you understand the binary-search-on-partition technique — a problem where the O(m+n) merge approach is obvious but the O(log) solution requires genuine insight.

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

Source citations

Public interview reports confirming this problem appears in Linear loops.

  • Glassdoor (2025-12)— Cited in Linear SWE onsite reports as a hard binary search question for senior roles.
  • Levels.fyi (2026-Q1)— Noted in Linear senior SWE interview write-ups as a stretch binary search problem.

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: [1,2,3]. Median is 2.

Example 2

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

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

Approaches

1. Merge then find median

Merge the two sorted arrays (like merge sort's merge step), then return the middle element.

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) {
    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 mid = Math.floor(merged.length / 2);
  return merged.length % 2 === 0 ? (merged[mid - 1] + merged[mid]) / 2 : merged[mid];
}

Tradeoff: O(m+n) time and space. Correct and easy to explain. The problem requires O(log(m+n)), so use this as a stepping stone only.

2. Partial merge (O(m+n) time, O(1) space)

Walk both arrays simultaneously without storing — stop at the median position.

Time
O(m + n)
Space
O(1)
function findMedianSortedArrays(nums1, nums2) {
  const total = nums1.length + nums2.length;
  const half = Math.floor(total / 2);
  let i = 0, j = 0, prev = 0, curr = 0;
  for (let k = 0; k <= half; k++) {
    prev = curr;
    if (i < nums1.length && (j >= nums2.length || nums1[i] <= nums2[j])) curr = nums1[i++];
    else curr = nums2[j++];
  }
  return total % 2 === 0 ? (prev + curr) / 2 : curr;
}

Tradeoff: O(m+n) time, O(1) space. Better than the full merge, but still linear. Not the O(log(m+n)) solution the problem requests.

3. Binary search on partition (optimal)

Binary search on the partition point of the smaller array. A valid partition means max(left halves) <= min(right halves).

Time
O(log(min(m, n)))
Space
O(1)
function findMedianSortedArrays(nums1, nums2) {
  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 partX = Math.floor((lo + hi) / 2);
    const partY = Math.floor((m + n + 1) / 2) - partX;
    const maxLeftX = partX === 0 ? -Infinity : nums1[partX - 1];
    const minRightX = partX === m ? Infinity : nums1[partX];
    const maxLeftY = partY === 0 ? -Infinity : nums2[partY - 1];
    const minRightY = partY === n ? Infinity : nums2[partY];
    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 = partX - 1;
    } else {
      lo = partX + 1;
    }
  }
}

Tradeoff: O(log(min(m,n))) — binary search on the smaller array only. Complex to get right. Explain the invariant first: 'I'm looking for a partition of both arrays such that everything on the left is <= everything on the right and the left halves total (m+n)/2 elements.'

Linear-specific tips

Don't jump straight to the O(log) solution — walk the progression. Linear interviewers at the senior level want to see the analysis first: 'O(m+n) merge is trivial. O(m+n) partial scan is better. The O(log) solution treats median-finding as finding the correct partition, which is a binary search problem.' If you explain the invariant clearly before coding, partial credit is guaranteed even if the code has minor bugs.

Common mistakes

  • Binary searching on both arrays instead of just the smaller one — search on the smaller to keep the range bounded.
  • Off-by-one in partition: the left half must contain exactly (m+n+1)/2 elements — the +1 handles odd totals.
  • Not guarding the out-of-bounds partition cases with -Infinity and Infinity.

Follow-up questions

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

  • What if the arrays are not sorted?
  • Kth Smallest Element in Two Sorted Arrays — generalize the median (which is the (m+n)/2-th element) to the kth element.
  • How does the solution change if there are more than two 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

What does 'partition' mean in this context?

A partition splits each array into a left half and a right half. A valid partition ensures max(left sides) <= min(right sides), giving us the combined sorted median.

Why binary search on the smaller array?

The partition of the smaller array (size m) uniquely determines the partition of the larger array. Binary searching on m values gives O(log m) — smaller and bounded.

Why +1 in (m+n+1)/2?

Integer division rounds down. Adding 1 ensures that for odd totals, the left half has the extra element — which is the median in that case.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →