4. Median of Two Sorted Arrays

hardAsked at Anduril

Find the median of two sorted arrays in O(log(m+n)) time. Anduril asks this hard problem to test binary-search-on-partition reasoning — the discipline of narrowing an answer space by invariant rather than by exhaustion, a mindset critical when searching configuration spaces in constrained autonomous planning.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in Anduril loops.

Glassdoor (2025-11)— Cited in Anduril senior SWE onsite threads as a binary-search hard problem that tests the ability to binary-search on a partition.
Blind (2025-09)— Anduril candidate reports describe this problem as appearing in advanced algorithm rounds for L4+ roles.

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: [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 then find median (O(m+n))

Merge the two arrays into a sorted combined array, then return the middle element(s). O(m+n) time — simpler but doesn't meet the O(log(m+n)) constraint.

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: Fails the O(log(m+n)) constraint. Present as a baseline to establish correctness, then pivot to the binary-search partition approach.

2. Binary search on partition (O(log(min(m,n))))

Binary-search for a partition of the smaller array such that the left halves of both arrays contain the correct median elements. Check the partition validity with max-left and min-right comparisons.

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;
  while (lo <= hi) {
    const cut1 = Math.floor((lo + hi) / 2); // elements from nums1 on the left
    const cut2 = Math.floor((m + n + 1) / 2) - cut1; // elements from nums2 on the left
    const l1 = cut1 === 0 ? -Infinity : nums1[cut1 - 1];
    const r1 = cut1 === m ? Infinity : nums1[cut1];
    const l2 = cut2 === 0 ? -Infinity : nums2[cut2 - 1];
    const r2 = cut2 === n ? Infinity : nums2[cut2];
    if (l1 <= r2 && l2 <= r1) {
      // Valid partition found
      if ((m + n) % 2 === 1) return Math.max(l1, l2);
      return (Math.max(l1, l2) + Math.min(r1, r2)) / 2;
    } else if (l1 > r2) {
      hi = cut1 - 1; // move cut1 left
    } else {
      lo = cut1 + 1; // move cut1 right
    }
  }
  return -1; // unreachable if inputs are valid sorted arrays
}

Tradeoff: O(log(min(m,n))) — the optimal solution. The hardest part is getting the invariants and sentinel values right. Walk the interviewer through the partition logic before coding.

Anduril-specific tips

Spend 5 minutes explaining the partition invariant before touching code: 'I want to find a cut in each array such that: (1) the combined left half has exactly (m+n+1)/2 elements, (2) all left elements are <= all right elements. The median is then max(l1,l2) for odd total or the average for even.' Anduril engineers value clarity over speed of coding. Use -Infinity and Infinity as sentinels for out-of-bounds cuts — it eliminates edge-case code. Binary search on nums1 (the smaller array) to keep the search space minimal.

Common mistakes

Not swapping arrays to ensure nums1 is smaller — the binary search range is [0, m], so binary searching the larger array is wasteful and risks out-of-bounds cuts on nums2.
Using 0 as the sentinel for empty partitions — it conflates with legitimate zero values in the input. Use -Infinity / Infinity.
Off-by-one in the total-left-half size — use floor((m+n+1)/2) to handle both odd and even total lengths uniformly.
Confusing which direction to move hi and lo — if l1 > r2, nums1's left side is too large: move cut1 left (hi = cut1-1). If l2 > r1, move cut1 right.

Follow-up questions

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

Find the kth smallest element from two sorted arrays (generalization of median).
What if the arrays are not sorted — would you sort them first or use a different strategy?
How would you extend this to find the median of k sorted arrays?

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?

The search range is [0, m]. Searching the smaller array keeps the range smaller and ensures cut2 never goes negative.

Why (m+n+1)/2 for the left-half size?

The +1 ensures that for odd total length, the left half has one more element (containing the median). For even length, both halves are equal. This formula works uniformly for both parities.

What do the -Infinity and Infinity sentinels represent?

-Infinity for l1/l2 means nums1/nums2 contributes nothing to the left half — any right element is valid. Infinity for r1/r2 means the array is exhausted on the right — any left element is valid.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →