Skip to main content

24. Median of Two Sorted Arrays

hardAsked at ServiceNow

Find the median of two sorted arrays in O(log(m+n)) time using binary search on partition points. ServiceNow asks this hard problem for senior roles because the binary-search-on-partition insight mirrors the data-partitioning reasoning required when merging sorted incident streams across multiple database shards.

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

Source citations

Public interview reports confirming this problem appears in ServiceNow loops.

  • Blind (2025)— Reported in ServiceNow senior SDE onsite as the hardest coding round question.
  • LeetCode Discuss (2026)— Flagged as a ServiceNow Staff engineer screen calibration problem.

Problem

Given two sorted arrays nums1 and nums2 of sizes m and n, return the median of the two sorted arrays. The overall runtime 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 (O(m+n)) and return the middle element(s).

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

Tradeoff: O(m+n) time and space — fails the O(log(m+n)) requirement. Acceptable only if the interviewer explicitly relaxes the constraint.

2. Binary search on partition

Binary search on the partition point in the smaller array. A correct partition has leftMax1 <= rightMin2 and leftMax2 <= rightMin1 — ensuring the left halves of both arrays combined form the lower half of the merged array. The median is computed 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;
  let lo = 0, hi = m;
  const half = Math.floor((m + n + 1) / 2);

  while (lo <= hi) {
    const i = Math.floor((lo + hi) / 2); // partition in nums1
    const j = half - i;                  // partition 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
      if ((m + n) % 2 === 1) return Math.max(maxLeft1, maxLeft2);
      return (Math.max(maxLeft1, maxLeft2) + 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. The -Infinity / +Infinity sentinel values for boundary partitions are critical: they handle the edge cases where one partition is at 0 or at the full array length without branching.

ServiceNow-specific tips

ServiceNow interviewers expect you to walk through the partition invariant — left sides combined are <= right sides combined — before touching code. Draw a diagram with four boundary values (maxLeft1, minRight1, maxLeft2, minRight2) and show how the binary search converges. The -Infinity/+Infinity sentinel trick is the candidate differentiator they explicitly look for.

Common mistakes

  • Binary searching on the larger array — correct but O(log(max)) instead of O(log(min)); interviewers notice.
  • Forgetting the +1 in the half calculation for odd total length — shifts the median element into the wrong half.
  • Not using -Infinity/+Infinity sentinels — requires four separate if-branches for edge partitions, which almost always has a bug.

Follow-up questions

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

  • K-th smallest element in two sorted arrays — generalize the half calculation to k.
  • Median of a stream of integers (LC 295) — maintain two heaps.
  • K-th largest element across N sorted arrays — use a min-heap of (value, array, index) tuples.

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

It minimizes the number of iterations from O(log(max(m,n))) to O(log(min(m,n))). For m=1 and n=10^9, this is 0 vs. 30 iterations — a 30x speedup.

What does 'correct partition' mean geometrically?

Imagine unzipping the merged sorted array in half. The left zip contains the i smallest from nums1 and the j = half - i smallest from nums2. A correct partition ensures no element from the left side is larger than any element from the right side — verified by the two cross-comparisons.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →