LeetCode #4 Hard

Median of Two Sorted Arrays

Return the median of two sorted arrays in O(log(min(n,m))).

binary-searcharraydivide-and-conquer

02

Intuition

💡

The median splits the union into equal halves. So find a cut of A and a cut of B whose left parts together hold half the elements, with everything left of the cuts ≤ everything right. Binary search where to cut A — B's cut is then forced.

03

Approach

1

Cut both arrays

Cut A at i and B at j with i + j = (n+m+1)//2. Left halves combined = half the union (the +1 favours the left for odd totals).

2

Valid cut condition

Need A[i−1] ≤ B[j] and B[j−1] ≤ A[i] (±∞ sentinels at the edges). If A[i−1] > B[j], the cut in A is too far right — move left.

3

Read off the median

Odd total: max of the left halves. Even: average of max(left) and min(right). Search only the shorter array for O(log min(n,m)).

04

Solution & live demo

python

▶1class Solution:
▶2    def findMedianSortedArrays(self, a, b):
▶3        if len(a) > len(b): a, b = b, a
▶4        n, m = len(a), len(b)
▶5        half = (n + m + 1) // 2
▶6        lo, hi = 0, n
▶7        INF = float("inf")
▶8        while True:
▶9            i = (lo + hi) // 2
▶10            j = half - i
▶11            a_left  = a[i-1] if i > 0 else -INF
▶12            a_right = a[i]   if i < n else INF
▶13            b_left  = b[j-1] if j > 0 else -INF
▶14            b_right = b[j]   if j < m else INF
▶15            if a_left <= b_right and b_left <= a_right:
▶16                if (n + m) % 2: return max(a_left, b_left)
▶17                return (max(a_left, b_left) + min(a_right, b_right)) / 2
▶18            if a_left > b_right: hi = i - 1
▶19            else: lo = i + 1

05

Edge cases

One array empty

Cut takes 0 from it; sentinels handle every comparison — median of the other array.

All of A before all of B

Search pushes i to n; sentinel +∞ on A's right keeps checks valid.

06

Complexity

Time

O(log min(n,m))

Space

O(1)

Partition search on the shorter array.