Skip to main content

90. Median of Two Sorted Arrays

hardAsked at Datadog

Find the median of two sorted arrays in O(log(min(m,n))). Datadog asks this for the partition-based binary search — same shape as quantile estimation over two pre-aggregated metric blocks.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — quantile estimation analog.

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

Example 2

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

Approaches

1. Merge both arrays

Merge sorted; pick middle.

Time
O(m + n)
Space
O(m + n)
// Standard merge sort merge; return median of merged.

Tradeoff: Linear — doesn't meet O(log) constraint.

2. Binary search partition (optimal)

Binary-search on the smaller array. Partition both arrays so left half has (m+n+1)/2 elements. Check the four boundary values.

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

Tradeoff: O(log min(m,n)). Datadog-canonical for quantile estimation across pre-sorted blocks.

Datadog-specific tips

Datadog grades on whether you can articulate the partition invariant: |left half| = (m+n+1)/2 and max(left) <= min(right). The binary search bisects on the partition point of the smaller array. Walk through this BEFORE coding.

Common mistakes

  • Binary searching the larger array — slower (still O(log)) but inefficient.
  • Using +Infinity instead of Number.POSITIVE_INFINITY in some languages — fine in JS but adversarial inputs can break.
  • Wrong half size — (m+n+1)/2 handles both parities cleanly.

Follow-up questions

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

  • Kth Smallest in Two Sorted Arrays — same partition idea.
  • Median of K sorted arrays — heap of k iterators.
  • Datadog-style: quantile across pre-aggregated blocks.

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 the smaller?

Search range is [0, min(m,n)]. Smaller = fewer iterations. Also avoids out-of-bounds.

What's the partition invariant?

Left half has exactly (m+n+1)/2 elements. Max of left <= min of right. The median is at this boundary.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →