Skip to main content

4. Median of Two Sorted Arrays

hard

Find the median of two sorted arrays in O(log(min(m, n))). The hardest binary-search problem in the canon — pattern is 'binary search on a partition'.

By Sam K., 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 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] and median is 2.

Example 2

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

Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Merge to a single array is O(m + n) — works, but the problem demands O(log).

Hint 2

Binary-search on a partition. Let half = (m + n + 1) / 2; choose i in [0, m] such that i elements come from nums1 and (half - i) from nums2.

Hint 3

The partition is valid iff nums1[i-1] <= nums2[j] and nums2[j-1] <= nums1[i]. Use ±INF for out-of-bounds.

Hint 4

If nums1[i-1] > nums2[j], reduce i. Otherwise increase i. Converge in log(min(m, n)) iterations.

Hint 5

Once valid, the median is max of left-side maxes (odd total) or average with min of right-side mins (even total).

Solution approach

Reveal approach

Ensure nums1 is the shorter array (swap if not) — that keeps the binary search range small. Let half = (m + n + 1) / 2. Binary search i in [0, m] for a valid partition: j = half - i, A_left = nums1[i-1] (-INF if i==0), A_right = nums1[i] (+INF if i==m), B_left = nums2[j-1] (-INF if j==0), B_right = nums2[j] (+INF if j==n). If A_left > B_right, search smaller i (hi = i - 1). If B_left > A_right, search larger i (lo = i + 1). Otherwise the partition is valid: if (m + n) is odd, return max(A_left, B_left); if even, return (max(A_left, B_left) + min(A_right, B_right)) / 2.0. O(log(min(m, n))) time, O(1) space.

Complexity

Time
O(log(min(m, n)))
Space
O(1)

Related patterns

  • binary-search
  • divide-and-conquer
  • partition

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft
  • Apple

More Binary Search practice problems

See all Binary Search problems →