Skip to main content

4. Median of Two Sorted Arrays

hardAsked at Akamai

Find the median of two sorted arrays in O(log(m+n)) time. Akamai asks this to test binary search mastery at its hardest — computing the p50 latency across two sorted measurement arrays without merging them maps directly to how distributed edge performance dashboards aggregate data from multiple regions.

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

Source citations

Public interview reports confirming this problem appears in Akamai loops.

  • Glassdoor (2025-12)— Akamai senior SWE interview reports cite this as a hard problem used to differentiate candidates in algorithm-heavy onsite rounds.
  • Blind (2025-10)— Akamai threads note this appears in senior-level interviews where binary search on two arrays is a key expectation.

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.00000

Explanation: Merged: [1,2,3]. Median is 2.

Example 2

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

Explanation: Merged: [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 to find the correct partition point such that the left half of both arrays combined contains exactly half of all elements, and max(leftHalf) <= min(rightHalf). The partition point in the second array is derived from the first.

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 = (m + n + 1) >> 1;
  let lo = 0, hi = m;
  while (lo <= hi) {
    const i = (lo + hi) >> 1; // 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) {
      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;
    } else {
      lo = i + 1;
    }
  }
}

Tradeoff: O(log min(m,n)) time, O(1) space. This is the only solution that satisfies the O(log(m+n)) constraint. It is conceptually difficult — Akamai expects candidates to explain the partition invariant before coding.

2. Merge and find median (O(m+n))

Merge both sorted arrays into one, then return the middle element. Simpler to implement, but O(m+n) time and space — does not satisfy the logarithmic 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 mid = merged.length >> 1;
  return merged.length % 2 === 1 ? merged[mid] : (merged[mid - 1] + merged[mid]) / 2;
}

Tradeoff: Correct but violates the O(log(m+n)) constraint. Present this as the baseline, then explain why we need binary search on the partition to achieve logarithmic time.

Akamai-specific tips

State the partition invariant in words before writing a single line of code: 'I want to find a partition of nums1 at index i and nums2 at index j = half - i, such that max(nums1[i-1], nums2[j-1]) <= min(nums1[i], nums2[j]). This means the left half contains exactly the smaller half of all elements, and the partition is correct.' Akamai expects depth of reasoning — if you can't articulate the invariant, implement the O(m+n) merge first and explain why it doesn't meet the constraint.

Common mistakes

  • Not ensuring nums1 is the smaller array — binary searching on the longer array gives worse bounds and complicates j = half - i bounds checking.
  • Using -Infinity and Infinity for boundary cases is correct — forgetting these guards causes out-of-bounds access at the array edges.
  • Off-by-one in the half calculation — for odd total length, half = (m+n+1)/2 ensures the left half is the larger half, keeping the median retrieval formula consistent.

Follow-up questions

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

  • Find the kth element of two sorted arrays — generalize from median (k = (m+n)/2) to any k.
  • How would you find the median of three sorted arrays?
  • How would you compute the p99 latency across two independently sorted measurement arrays from two server clusters?

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 nums1 and not nums2?

We always binary search on the smaller array to minimize iterations. The partition in nums2 is fully determined by the partition in nums1 (j = half - i), so we only need to search one.

Why +1 in half = (m+n+1)/2?

For odd total length, this ensures the left partition has one more element than the right. The median is then max(leftHalf) without averaging. For even length, the +1 ties out when dividing by 2.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →