Skip to main content

81. Median of Two Sorted Arrays

hardAsked at Snowflake

Find the median of two sorted arrays in O(log(min(m, n))). Snowflake asks this to test binary search on partitions — directly relevant to merging sorted micro-partitions for median computation during APPROX_PERCENTILE follow-up.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake execution-engine team uses this to set up APPROX_PERCENTILE discussion.
  • LeetCode Discuss (2025-10)— Reported at Snowflake SDE-II onsites.

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, 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

Example 2

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

Approaches

1. Merge and pick middle

Merge into a single sorted array. Return middle element(s).

Time
O(m + n)
Space
O(m + n)
// outline only — linear, doesn't meet the log requirement.

Tradeoff: Linear. Mention only as the baseline.

2. Binary search on the partition (optimal)

Always search on the smaller array. Pick partition i. Compute j = (m+n+1)/2 - i. Validate left max <= right min on both sides; adjust i via binary search.

Time
O(log(min(m, n)))
Space
O(1)
function findMedianSortedArrays(a, b) {
  if (a.length > b.length) return findMedianSortedArrays(b, a);
  const m = a.length, n = b.length;
  let lo = 0, hi = m;
  while (lo <= hi) {
    const i = (lo + hi) >>> 1;
    const j = ((m + n + 1) >>> 1) - i;
    const aLeft = i === 0 ? -Infinity : a[i - 1];
    const aRight = i === m ? Infinity : a[i];
    const bLeft = j === 0 ? -Infinity : b[j - 1];
    const bRight = j === n ? Infinity : b[j];
    if (aLeft <= bRight && bLeft <= aRight) {
      if ((m + n) % 2 === 1) return Math.max(aLeft, bLeft);
      return (Math.max(aLeft, bLeft) + Math.min(aRight, bRight)) / 2;
    }
    if (aLeft > bRight) hi = i - 1;
    else lo = i + 1;
  }
}

Tradeoff: True O(log(min(m, n))). The key insight: a 'median partition' splits both arrays into left and right halves with the right properties.

Snowflake-specific tips

Snowflake interviewers grade this on whether you reach the partition-search formulation. Bonus signal: pivot to APPROX_PERCENTILE — Snowflake uses t-digest sketches that merge partial sketches via a similar partition-based combine.

Common mistakes

  • Searching the larger array — slower (log of the larger).
  • Off-by-one when computing j = (m+n+1)/2 - i — must use ceiling division for odd totals.
  • Forgetting the +/-Infinity sentinels for partitions at the boundaries.

Follow-up questions

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

  • Find K-th element in two sorted arrays.
  • Median of k sorted arrays.
  • How does t-digest work in APPROX_PERCENTILE?

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-searching the smaller array gives log of the smaller size — faster when m and n differ greatly.

Why (m+n+1)/2?

For odd m+n, the median is the (m+n+1)/2-th element. For even, we average the m+n/2 and m+n/2+1-th. The +1 keeps the formula uniform.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →