DSA problem
Median of Two Sorted Arrays
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(min(m, n))).
The merge-and-pick approach is O(m + n) and easy, but the O(log(min(m, n))) bound demands a much sharper idea: binary search the partition. The median of a combined sorted array of size m + n is determined by which (m + n + 1) / 2 elements end up in the "left" half. If you pick a partition index i in nums1 and j = (m + n + 1) / 2 - i in nums2, then nums1[0..i-1] + nums2[0..j-1] is the left half (size (m + n + 1) / 2) and the remaining elements form the right half.
For the partition to be valid (i.e., the union is sorted across the cut), two cross-inequalities must hold simultaneously: nums1[i - 1] <= nums2[j] and nums2[j - 1] <= nums1[i]. Binary search i in [0, m] on nums1 (the smaller array — swap inputs if m > n). At each midpoint, check the inequalities: if nums1[i - 1] > nums2[j], then i is too large, narrow right; otherwise narrow left.
Use sentinels -∞ (when an index is 0) and +∞ (when an index equals array length) to handle the partition's boundaries uniformly. When the valid partition is found, the median is either max(nums1[i-1], nums2[j-1]) for odd total length, or the average of max(left) and min(right) for even total length. Running time O(log(min(m, n))) and O(1) space.
Examples
nums1 = [1,3], nums2 = [2]2.00000nums1 = [1,2], nums2 = [3,4]2.50000nums1 = [0,0], nums2 = [0,0]0.00000Constraints
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -10^6 <= nums1[i], nums2[i] <= 10^6
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.