Skip to main content

4. Median of Two Sorted Arrays

hardAsked at Gusto

Find the median of two sorted arrays in O(log(m+n)). Gusto asks this for senior roles to test binary search reasoning under pressure — they want the binary search on partitions approach, and they watch whether you can maintain the invariant clearly without devolving into case chaos.

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

Source citations

Public interview reports confirming this problem appears in Gusto loops.

  • Glassdoor (2025-11)— Cited in Gusto senior SWE reports as an occasional hard problem used to distinguish senior from staff-level candidates.
  • Blind (2025-10)— Gusto threads mention this problem appears rarely but serves as a strong differentiator in staff-engineer loops.

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 array = [1,2,3]. Median = 2.

Example 2

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

Explanation: Merged array = [1,2,3,4]. Median = (2+3)/2 = 2.5.

Approaches

1. O(log(min(m,n))) binary search on partition

Binary search on the shorter array to find a partition point. The partition divides both arrays such that all left-side elements are ≤ all right-side elements. The median is derived from the boundary values.

Time
O(log(min(m, n)))
Space
O(1)
function findMedianSortedArrays(nums1, nums2) {
  // ensure nums1 is the shorter array for binary search
  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 partition1 = Math.floor((lo + hi) / 2);
    const partition2 = Math.floor((m + n + 1) / 2) - partition1;
    const maxLeft1  = partition1 === 0 ? -Infinity : nums1[partition1 - 1];
    const minRight1 = partition1 === m ?  Infinity : nums1[partition1];
    const maxLeft2  = partition2 === 0 ? -Infinity : nums2[partition2 - 1];
    const minRight2 = partition2 === n ?  Infinity : nums2[partition2];
    if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
      // correct partition found
      if ((m + n) % 2 === 0) {
        return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;
      } else {
        return Math.max(maxLeft1, maxLeft2);
      }
    } else if (maxLeft1 > minRight2) {
      hi = partition1 - 1; // move partition1 left
    } else {
      lo = partition1 + 1; // move partition1 right
    }
  }
}

Tradeoff: O(log(min(m,n))) time, O(1) space. The optimal solution. Requires careful reasoning about boundary conditions — use Infinity/-Infinity sentinels to handle empty partitions cleanly.

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

Merge both arrays fully (like merge sort), then find the median. Simple to implement but doesn't meet the O(log(m+n)) requirement.

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

Tradeoff: Easy to implement and verify correctness. Use this to confirm your binary search result or to establish a baseline. State that this doesn't meet the O(log) requirement before presenting it.

Gusto-specific tips

Start by stating the O(m+n) merge approach clearly, then pivot: 'The problem requires O(log(m+n)), so I need binary search. The key insight is to binary search on a partition of the shorter array.' Walk through the partition invariant before any code — Gusto interviewers will follow the reasoning more than the syntax. Use -Infinity/+Infinity to handle edge partitions cleanly — don't special-case them.

Common mistakes

  • Binary searching on the longer array — produces O(log(max(m,n))) which is correct but slightly slower; always search the shorter array.
  • Off-by-one in partition2 = (m+n+1)/2 - partition1 — the +1 is essential for odd-total arrays.
  • Not handling empty partitions (partition = 0 or partition = array length) — must use -Infinity and +Infinity as sentinels.
  • Computing the median incorrectly for even vs odd total length — even: average of the two middle values; odd: the maximum of left boundaries.

Follow-up questions

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

  • Find the kth smallest element in two sorted arrays — generalization of the same technique.
  • Find the median of a stream of integers (LC 295) — entirely different approach using two heaps.
  • How would you extend this to three 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 search the shorter array?

Binary search on the shorter array guarantees partition2 stays valid (between 0 and n). Searching the longer array could result in partition2 < 0.

What does partition1 = 3 mean?

The first 3 elements of nums1 are in the 'left half' of the merged array. nums1[partition1 - 1] is the rightmost element on the left side from nums1.

Why does the +1 appear in (m+n+1)/2?

It ensures that for an odd total, the left half has one more element than the right half. The median is then max(maxLeft1, maxLeft2) — the largest left-side element.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →