Skip to main content

4. Median of Two Sorted Arrays

hardAsked at Citadel

This is perhaps the most technically demanding standard LeetCode hard — O(log(min(m,n))) requires a binary search on partition points, not on values. Citadel asks it to separate candidates who understand binary search at a deep level from those who merely know it as a lookup pattern. Precise handling of odd/even total length and boundary conditions is non-negotiable.

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

Source citations

Public interview reports confirming this problem appears in Citadel loops.

  • Glassdoor (2025-11)— Citadel SWE on-site reports cite Median of Two Sorted Arrays as an occasional hard-round problem used to test binary search depth.
  • Blind (2025-08)— Citadel SWE threads note this problem appears in senior SWE interviews specifically to probe O(log n) binary search 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. O(log(m+n)) merge simulation

Use a count-based approach: advance pointers through the two arrays (without merging) to find the (m+n)/2-th element. O(m+n) time — not optimal but worth stating as a baseline.

Time
O(m+n)
Space
O(1)
function findMedianSortedArrays(nums1, nums2) {
  // O(m+n) approach: simulate merge to find median element(s)
  const total = nums1.length + nums2.length;
  const half = Math.floor(total / 2);
  let i = 0, j = 0, prev = 0, curr = 0;
  for (let k = 0; k <= half; k++) {
    prev = curr;
    if (i < nums1.length && (j >= nums2.length || nums1[i] <= nums2[j])) {
      curr = nums1[i++];
    } else {
      curr = nums2[j++];
    }
  }
  return total % 2 === 0 ? (prev + curr) / 2 : curr;
}

Tradeoff: O(m+n) time — straightforward but doesn't meet the O(log(m+n)) requirement. Present this first to show you understand the problem, then drive to the binary-search approach.

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

Binary search on the partition index in the shorter array. Find the partition such that the left halves of both arrays together form the lower half of the merged array. All left elements ≤ all right elements.

Time
O(log(min(m,n)))
Space
O(1)
function findMedianSortedArrays(nums1, nums2) {
  // Always binary-search on the shorter 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); // size of left partition

  let lo = 0, hi = m;
  while (lo <= hi) {
    const partA = (lo + hi) >> 1; // partition in nums1
    const partB = half - partA;   // partition in nums2

    const maxLeftA  = partA === 0 ? -Infinity : nums1[partA - 1];
    const minRightA = partA === m ?  Infinity : nums1[partA];
    const maxLeftB  = partB === 0 ? -Infinity : nums2[partB - 1];
    const minRightB = partB === n ?  Infinity : nums2[partB];

    if (maxLeftA <= minRightB && maxLeftB <= minRightA) {
      // Correct partition found
      if ((m + n) % 2 === 1) {
        return Math.max(maxLeftA, maxLeftB);
      }
      return (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2;
    } else if (maxLeftA > minRightB) {
      hi = partA - 1; // move partition in A left
    } else {
      lo = partA + 1; // move partition in A right
    }
  }
  return -1; // unreachable for valid input
}

Tradeoff: O(log(min(m,n))) — the optimal solution. Conceptually complex: binary search on partition index, not on values. The -Infinity / +Infinity sentinels elegantly handle boundary cases (partition at edge of array). This is the answer Citadel grades as excellent.

Citadel-specific tips

Start by stating: 'The naive merge is O(m+n). The O(log) solution binary searches on a partition index, not on values — it finds the split point where the left halves of both arrays together form exactly half of the merged array.' Then explain the two invariants that define a valid partition: (1) maxLeftA ≤ minRightB and (2) maxLeftB ≤ minRightA. Citadel interviewers will push on why you binary search on the shorter array — 'Because partB = half - partA; if m > n, partB could go negative, violating array bounds.' This level of boundary reasoning is what separates excellent candidates.

Common mistakes

  • Binary searching on the longer array — can cause partB to be negative (out of bounds).
  • Using 0 and n as sentinels instead of -Infinity and +Infinity — causes incorrect comparisons when the partition is at the edge of an array.
  • Computing half as (m+n)/2 (integer division) instead of (m+n+1)/2 — fails for odd total length (you want the left half to be the larger half).
  • Not handling the even/odd total length distinction for the final return — even returns average of max-left and min-right; odd returns max-left.

Follow-up questions

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

  • Kth Smallest Element in Two Sorted Arrays — generalization of median (k = (m+n+1)/2).
  • What if you had 3 sorted arrays?
  • How would you find the k-th percentile instead of the median?

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 partition index and not on a value?

The partition index uniquely determines which elements are in the left half. Binary searching on values would require knowing what value corresponds to the median — circular reasoning. Searching on the index and checking the partition invariants directly solves the problem.

Why use half = (m+n+1)/2 instead of (m+n)/2?

For odd total length, (m+n)/2 and (m+n+1)/2 differ by 1. Using (m+n+1)/2 ensures the left partition is the same size or one larger than the right, which simplifies the final return: for odd length, just take max of the left sides.

What does -Infinity sentinel represent?

When partA = 0, there are no elements in nums1's left partition — the effective maximum is -Infinity (any element from nums2 is ≥ it). Similarly, Infinity represents an empty right partition.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →