Skip to main content

23. Median of Two Sorted Arrays

hardAsked at Gojek

Find the median of the union of two sorted arrays in logarithmic time.

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

Problem

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall runtime complexity should be O(log(min(m, n))).

Constraints

  • 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

Example 2

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

Approaches

1. Merge and pick middle

Merge into a new sorted array and read the middle.

Time
O(m+n)
Space
O(m+n)
const merged = [];
let i = 0, j = 0;
while (i < m && j < n) merged.push(nums1[i] < nums2[j] ? nums1[i++] : nums2[j++]);
while (i < m) merged.push(nums1[i++]);
while (j < n) merged.push(nums2[j++]);

Tradeoff:

2. Binary search the partition

Binary search a partition index in the shorter array so that left halves of both arrays together have (m+n+1)/2 elements and every left element is <= every right element. The median is read from the partition boundary.

Time
O(log(min(m,n)))
Space
O(1)
function findMedianSortedArrays(a, b) {
  if (a.length > b.length) [a, b] = [b, a];
  const m = a.length, n = b.length, half = (m + n + 1) >> 1;
  let lo = 0, hi = m;
  while (lo <= hi) {
    const i = (lo + hi) >> 1, j = half - i;
    const aL = i ? a[i-1] : -Infinity, aR = i < m ? a[i] : Infinity;
    const bL = j ? b[j-1] : -Infinity, bR = j < n ? b[j] : Infinity;
    if (aL <= bR && bL <= aR) {
      if ((m + n) % 2) return Math.max(aL, bL);
      return (Math.max(aL, bL) + Math.min(aR, bR)) / 2;
    } else if (aL > bR) hi = i - 1; else lo = i + 1;
  }
}

Tradeoff:

Gojek-specific tips

Gojek hard rounds reward candidates who can articulate the partition invariant aloud, which mirrors how their multi-service teams reason about quantile estimation across regional shards.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →