Median of Two Sorted Arrays LeetCode 4

LeetCode 4 — Median of Two Sorted Arrays — gives you two sorted arrays nums1 and nums2 of sizes m and n. Return the median of the two arrays combined. The overall run time complexity should be O(log(min(m, n))).

The median of a sorted array of length L is the middle element if L is odd, or the average of the two middle elements if L is even. Merging both arrays and finding the middle would be O(m+n), but the problem demands O(log(min(m,n))).

This is considered one of the hardest problems on LeetCode. The binary search approach partitions both arrays simultaneously, finding the correct split point where the left halves combine to form the lower half of the merged array. The median sits at the partition boundary.

Imagine the merged sorted array of length m+n. The median depends on the (m+n+1)/2 smallest elements (the left half). We need to split nums1 into a left part of size i and nums2 into a left part of size j, where i + j = (m+n+1)/2.

If we choose i elements from nums1, then j = (m+n+1)/2 - i from nums2. The partition is correct when: maxLeft1 <= minRight2 AND maxLeft2 <= minRight1. This ensures every element in the combined left half is <= every element in the right half.

Binary search on i (from 0 to m): if maxLeft1 > minRight2, i is too large — search left. If maxLeft2 > minRight1, i is too small — search right. When both conditions are met, the median is at the boundary.

After finding the correct partition i and j: maxLeft1 = nums1[i-1] (or -infinity if i=0), minRight1 = nums1[i] (or +infinity if i=m). Similarly maxLeft2 = nums2[j-1] and minRight2 = nums2[j].

If (m+n) is odd, the median is max(maxLeft1, maxLeft2) — the largest element in the left half. If (m+n) is even, the median is (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0.

The infinity sentinels handle edge cases where all elements of one array are in the left or right half. When i=0, no elements from nums1 are in the left half, so maxLeft1 = -infinity (never constrains). When i=m, all of nums1 is in the left half, so minRight1 = +infinity.

Consider nums1 = [1, 3], nums2 = [2]. m=2, n=1. half = (2+1+1)/2 = 2. Binary search i in [0, 2]. Try i=1: j=2-1=1. maxLeft1=nums1[0]=1, minRight1=nums1[1]=3. maxLeft2=nums2[0]=2, minRight2=+inf.

Check: maxLeft1=1 <= minRight2=inf OK. maxLeft2=2 <= minRight1=3 OK. Partition found! (m+n)=3 is odd. Median = max(1, 2) = 2.0. Correct — merged [1, 2, 3], median is 2.

Consider nums1 = [1, 2], nums2 = [3, 4]. m=2, n=2. half=2. Try i=1: j=1. maxLeft1=1, minRight1=2. maxLeft2=3, minRight2=4. Check: 1<=4 OK, 3<=2 FAIL. i too small, search right. Try i=2: j=0. maxLeft1=2, minRight1=inf. maxLeft2=-inf, minRight2=3. Check: 2<=3 OK, -inf<=inf OK. Even: (max(2,-inf) + min(inf,3))/2 = (2+3)/2 = 2.5.

Python: if m > n: swap. lo, hi = 0, m. half = (m+n+1)//2. While lo <= hi: i = (lo+hi)//2. j = half - i. Compute four boundary values with -inf/inf guards. If maxLeft1 > minRight2: hi = i-1. Elif maxLeft2 > minRight1: lo = i+1. Else: compute and return median.

Java: same logic with Integer.MIN_VALUE/MAX_VALUE as sentinels. Use double for the return type. Ensure nums1 is the shorter array with an initial swap check.

Common mistakes: (1) not swapping to ensure searching the shorter array, (2) wrong half calculation (use (m+n+1)/2 for correct rounding), (3) missing infinity guards for edge partitions.

Time: O(log(min(m, n))). Binary search on the shorter array. Each iteration is O(1) with at most log(min(m,n)) iterations. This meets the problem's strict time requirement.

Space: O(1). Only a constant number of variables: lo, hi, i, j, and the four boundary values. No auxiliary arrays or data structures.

This is optimal — any comparison-based algorithm for this problem requires Ω(log(min(m,n))) comparisons. The binary search achieves this lower bound exactly.

Kth Smallest Element in a Sorted Matrix (LeetCode 378) uses binary search on the value range with a counting function. The concept of binary searching on a derived quantity (partition position, value range) is shared.

Find Minimum in Rotated Sorted Array (LeetCode 153) and Search in Rotated Sorted Array (LeetCode 33) also apply binary search to non-obvious search spaces. Together with Median of Two Sorted Arrays, they form the advanced binary search trilogy.

Merge Two Sorted Lists (LeetCode 21) and Merge K Sorted Lists (LeetCode 23) solve the merging problem directly. Understanding the merge operation helps visualize what the partition in Median of Two Sorted Arrays achieves without actually merging.