How do you approach Median of Two Sorted Arrays?

Use binary search on the smaller array.

What is the time complexity of Median of Two Sorted Arrays?

Time complexity: O(log(min(m, n))). Space complexity: O(1).

What are common mistakes on Median of Two Sorted Arrays?

Computing the midpoint as (low + high) / 2. In a fixed-width integer language that overflows on large ranges; low + (high - low) / 2 does not. An update that fails to shrink the range, which spins forever on a two-element window. Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.

gitGood.dev

← Back to problems

Median of Two Sorted Arrays

HardAlgorithms

Description

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

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.

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

Median of Two Sorted Arrays: approach, complexity and pitfalls

A hard binary search problem, graded against 6 test cases (3 of them hidden).

The pattern: Binary Search

Halving a search space each step - on sorted arrays, and on answers themselves.

Reach for it when you see: A sorted input, or a monotonic "is this value feasible?" predicate you can binary search over.

More Binary Searchproblems →

If you are stuck

Show the 3-step hint ladder

Use binary search on the smaller array.
Find a partition where all left elements are ≤ all right elements.
The partition position gives us the median directly.

The optimal approach

Show the approach: Binary Search on Partition

Binary search to find the correct partition in the smaller array. The partition divides both arrays such that all left elements ≤ all right elements.

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

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.

Common Binary Search mistakes

These apply to the pattern as a whole, not just this problem.

Computing the midpoint as `(low + high) / 2`. In a fixed-width integer language that overflows on large ranges; `low + (high - low) / 2` does not.
An update that fails to shrink the range, which spins forever on a two-element window.
Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.