Median of Two Sorted Arrays
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
Problem
Given two individually sorted arrays of sizes m and n, return the median of all their elements combined. The overall run time must be O(log(m + n)), so merging the arrays is not allowed.
Examples
Constraints
- • 0 <= m, n <= 1000
- • 1 <= m + n <= 2000
- • Both arrays are sorted ascending
Hints & approach
Hint 1
The median splits the combined data into a left half and a right half of equal size.
Hint 2
If you choose how many elements the left half takes from nums1, the count from nums2 is forced.
Hint 3
Binary search that cut in the shorter array until every left value is <= every right value.
Approachtry the hints first
Binary search a partition index i in the shorter array A; the partner index in B is j = (m + n + 1) / 2 - i, so the left side always holds half the elements. The partition is valid when A[i-1] <= B[j] and B[j-1] <= A[i] (treat out-of-range as -infinity / +infinity). If A[i-1] is too big, move i left; if B[j-1] is too big, move i right. Once valid, the median is max(A[i-1], B[j-1]) for an odd total, or the average of that and min(A[i], B[j]) for an even total. Searching only the shorter array gives O(log min(m, n)).
Time O(log min(m, n)) · Space O(1)
