Skip to main content

4. Median of Two Sorted Arrays

hardAsked at Elastic

Find the median of two sorted arrays in O(log(m+n)) time. Elastic includes this hard problem because computing global percentiles across distributed shards — a core Elasticsearch aggregation feature — requires exactly this kind of partitioned-binary-search reasoning over sorted shard segments.

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

Source citations

Public interview reports confirming this problem appears in Elastic loops.

  • Glassdoor (2025-11)— Elastic senior SWE candidates report binary search on partitioned arrays appearing in the harder onsite rounds.
  • Blind (2025-09)— Median of Two Sorted Arrays cited in Elastic senior interview threads as a problem that directly tests distributed-percentile reasoning.

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. Binary search on partition (O(log min(m,n)))

Binary search on the smaller array. At each step, partition both arrays so that the left halves together contain (m+n+1)/2 elements. Check that maxLeft1 <= minRight2 and maxLeft2 <= minRight1. Adjust the partition until this invariant holds, then compute the median from the four boundary values.

Time
O(log min(m, n))
Space
O(1)
function findMedianSortedArrays(nums1, nums2) {
  // Ensure nums1 is the smaller array
  if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
  const m = nums1.length, n = nums2.length;
  const half = Math.floor((m + n + 1) / 2);
  let lo = 0, hi = m;
  while (lo <= hi) {
    const i = Math.floor((lo + hi) / 2); // partition index in nums1
    const j = half - i;                  // partition index in nums2
    const maxLeft1  = i === 0 ? -Infinity : nums1[i - 1];
    const minRight1 = i === m ?  Infinity : nums1[i];
    const maxLeft2  = j === 0 ? -Infinity : nums2[j - 1];
    const minRight2 = j === n ?  Infinity : nums2[j];
    if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
      // Correct partition
      const maxLeft = Math.max(maxLeft1, maxLeft2);
      if ((m + n) % 2 === 1) return maxLeft;
      return (maxLeft + Math.min(minRight1, minRight2)) / 2;
    } else if (maxLeft1 > minRight2) {
      hi = i - 1; // move partition left in nums1
    } else {
      lo = i + 1; // move partition right in nums1
    }
  }
}

Tradeoff: O(log min(m,n)) — optimal per the problem's requirement. The partition invariant is the hardest insight: every element on the left of the virtual partition must be <= every element on the right.

2. Merge and find (O(m+n)) — baseline

Merge both arrays linearly, then return the median element. O(m+n) time — violates the logarithmic requirement but useful to establish correctness.

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 === 1 ? merged[mid] : (merged[mid - 1] + merged[mid]) / 2;
}

Tradeoff: Simple to verify correctness. Always present this first, then explain why O(log(m+n)) is needed and derive the binary search solution.

Elastic-specific tips

Start with the O(m+n) merge to prove correctness, then pivot: 'The O(log) constraint forces binary search. The insight is to binary search on the partition point in the smaller array — each partition implies a corresponding partition in the larger array, and we check whether elements cross the partition boundary correctly.' Connect to the domain: 'Elasticsearch's percentile aggregation faces this exact problem across shards — computing the global p99 requires partitioning sorted per-shard histograms, which uses a similar rank-based binary search.'

Common mistakes

  • Not swapping to ensure nums1 is smaller — binary search space is [0, m] so m must be the smaller length.
  • Off-by-one in the half computation — use (m+n+1)/2 (floor) so the left half gets the extra element in odd-total cases.
  • Not handling edge partitions with -Infinity/+Infinity sentinels — i=0 means no elements from nums1 on the left.
  • Returning the wrong value for even-total arrays — average the two middle values.

Follow-up questions

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

  • K-th Smallest Element in Two Sorted Arrays — generalize to finding any percentile, not just the median.
  • K-th Smallest Element in a Sorted Matrix (LC 378) — binary search on value rather than index.
  • How does Elasticsearch compute global percentile ranks across distributed shard histograms?

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

Binary search space is [0, m]. Searching on the smaller array guarantees the corresponding j = half - i is always a valid index in nums2.

What does the partition invariant mean?

At the correct partition, every element on the combined left side must be less than or equal to every element on the combined right side: maxLeft1 <= minRight2 AND maxLeft2 <= minRight1.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →