Skip to main content

26. Median of Two Sorted Arrays

hardAsked at Square

Find the median settlement time across two independently sorted streams of payment batches — Square's treasury team computes this real-time percentile across bank ACH and card-network queues to hit SLA commitments without merging two large sorted logs.

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

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 must 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 = 2.

Example 2

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

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

Approaches

1. Merge and find median

Merge both arrays (like merge-sort step), then read the middle element(s). O(m + n) time and space — correct but violates the 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) {
    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:

2. Binary search on partition

Binary search on the partition point of the smaller array. For each partition, the left halves of both arrays must be <= right halves. Handle even/odd total length. O(log(min(m,n))).

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 px = Math.floor((lo + hi) / 2);
    const py = Math.floor((m + n + 1) / 2) - px;
    const maxX = px === 0 ? -Infinity : nums1[px - 1];
    const minX = px === m ? Infinity  : nums1[px];
    const maxY = py === 0 ? -Infinity : nums2[py - 1];
    const minY = py === n ? Infinity  : nums2[py];
    if (maxX <= minY && maxY <= minX) {
      const leftMax = Math.max(maxX, maxY);
      if ((m + n) % 2 === 1) return leftMax;
      return (leftMax + Math.min(minX, minY)) / 2;
    } else if (maxX > minY) hi = px - 1;
    else lo = px + 1;
  }
}

Tradeoff:

Square-specific tips

This is a Square Staff/Senior bar question. They do not expect most candidates to derive the binary-search partition from scratch — they grade whether you can (1) clearly state why O(m+n) merge violates the constraint, (2) articulate the partition invariant in English before touching code, and (3) correctly handle edge cases like empty arrays and even/odd total lengths. Walk the invariant — 'left partition elements from both arrays must all be <= right partition elements' — before writing a single line.

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

Practice these live with InterviewChamp.AI →