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

Practice these live with InterviewChamp.AI

Drill Median of Two Sorted Arrays and Binary Search problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →