Median Two Sorted Arrays LeetCode 4

LeetCode 4 Median of Two Sorted Arrays is the first hard problem on LeetCode and one of the most famous interview questions in software engineering. Given two sorted arrays nums1 of size m and nums2 of size n, you must find the median of the combined array formed by merging them. The overall runtime complexity must be O(log(m+n)) — not O(m+n) — which is what makes this problem genuinely hard and interesting.

The median is defined as the middle value when the combined array is sorted. If the total number of elements m+n is odd, the median is the single middle element. If m+n is even, the median is the average of the two middle elements. For example, if nums1 = [1, 3] and nums2 = [2], the merged array is [1, 2, 3] and the median is 2. If nums1 = [1, 2] and nums2 = [3, 4], the merged array is [1, 2, 3, 4] and the median is (2 + 3) / 2 = 2.5.

The O(log(m+n)) time constraint rules out the naive approach of merging both arrays and picking the middle element — that would be O(m+n). The key insight is that we do not need to merge the arrays at all. Instead, we use binary search to directly find where to partition both arrays such that the left halves together contain exactly the correct number of elements and every left element is smaller than or equal to every right element.

The most straightforward approach to find the median of two sorted arrays is to merge them using the merge step from merge sort — the same two-pointer technique that combines two sorted arrays into one sorted array. Once merged, you pick the middle element (odd total) or average the two middle elements (even total). This runs in O(m+n) time and O(m+n) space, and it is trivially correct.

The problem explicitly requires O(log(m+n)) time, which rules out the merge approach. Logarithmic time on a problem involving arrays of sizes m and n strongly hints at binary search. Any time you see O(log n) in a problem that involves searching, the answer almost certainly involves binary search — either on the input array itself, or on the answer space. For this problem, we binary search on the partition index of the shorter array.

Even if you use a smarter merge that stops at the middle index (the "find the k-th smallest" approach), you still end up with O(log(m+n)) recursive calls each doing O(1) work, which achieves the required complexity. However, the cleanest O(log min(m,n)) solution uses direct binary search on the partition of the shorter array — one pass, no recursion, constant space.

The key insight is that finding the median is equivalent to finding the correct way to partition both arrays simultaneously. Imagine splitting nums1 at index i and nums2 at index j such that nums1[0..i-1] and nums2[0..j-1] form the "left half" of the combined array, while nums1[i..m-1] and nums2[j..n-1] form the "right half". For this partition to represent the median, two conditions must hold: the left half must contain exactly the right number of elements, and every element in the left half must be less than or equal to every element in the right half.

The left half should contain (m+n+1)/2 elements total (using integer division). The +1 handles the odd-length case, ensuring the left half gets the extra middle element when m+n is odd. If we decide to pick i elements from nums1 for the left half, we automatically need j = (m+n+1)/2 - i elements from nums2. This means i entirely determines j — we only have one degree of freedom, which is exactly what makes binary search applicable.

The partition is valid when nums1[i-1] <= nums2[j] AND nums2[j-1] <= nums1[i]. The first condition says the largest element in nums1's left portion does not exceed the smallest element in nums2's right portion. The second condition says the largest element in nums2's left portion does not exceed the smallest element in nums1's right portion. Together, these two cross-comparisons guarantee that all left elements are <= all right elements.

With the partition insight in place, the algorithm is a standard binary search on i from 0 to m. Initialize lo = 0 and hi = m. At each step, compute i = (lo + hi) // 2 and j = half - i. Then check whether the partition is valid using the two cross-comparisons. If nums1[i-1] > nums2[j], the left portion of nums1 is too large and we need to shrink it by moving hi = i - 1. If nums2[j-1] > nums1[i], the left portion of nums2 is too large and we need to grow i by moving lo = i + 1.

The binary search terminates when the partition is valid — when nums1[i-1] <= nums2[j] AND nums2[j-1] <= nums1[i]. Because nums1 and nums2 are individually sorted, every time we adjust i in one direction the cross-conditions move monotonically toward validity. This is the property that guarantees binary search converges to the correct answer: the "invalid" and "valid" regions of the search space are cleanly separated, with the valid partition at the boundary.

The total number of iterations is O(log m) where m is the length of the shorter array. Since we ensured m <= n at the start, this is O(log min(m,n)). Each iteration does O(1) work — two comparisons, two index computations, one boundary update. The overall time complexity is O(log min(m,n)) and the space complexity is O(1) since no additional data structures are needed.

Once the correct partition is found, computing the median is straightforward. The left half consists of nums1[0..i-1] and nums2[0..j-1]. The largest element on the left side is max(nums1[i-1], nums2[j-1]). The right half consists of nums1[i..m-1] and nums2[j..n-1]. The smallest element on the right side is min(nums1[i], nums2[j]). For an odd total (m+n is odd), the median is the largest element on the left side — max(nums1[i-1], nums2[j-1]). For an even total, the median is the average of the largest left element and the smallest right element.

Edge cases arise when i = 0, meaning no elements are taken from nums1 for the left half, so there is no nums1[i-1] to compare. Similarly, when i = m, nums1 contributes all its elements to the left half and nums1[i] does not exist. The same applies to j = 0 and j = n for nums2. To handle these cleanly, use sentinel values: when i = 0, treat nums1[i-1] as negative infinity; when i = m, treat nums1[i] as positive infinity. Apply the same logic for j with respect to nums2.

With sentinel values in place, the median formula works uniformly regardless of edge cases. In Python you can use float('-inf') and float('inf'). In Java, use Integer.MIN_VALUE and Integer.MAX_VALUE. The formula for odd total is max_left = max(left1, left2) where left1 = nums1[i-1] if i > 0 else -inf. For even total, median = (max_left + min_right) / 2.0 where min_right = min(right1, right2) and right1 = nums1[i] if i < m else +inf.

The Python implementation is about 20 lines. Swap nums1 and nums2 if len(nums1) > len(nums2). Set m, n = len(nums1), len(nums2) and half = (m + n + 1) // 2. Binary search lo, hi = 0, m. Inside the while loop: i = (lo + hi) // 2, j = half - i. Set left1, left2, right1, right2 using the sentinel pattern. If left1 > right2: hi = i - 1. Elif left2 > right1: lo = i + 1. Else: break. After the loop, compute max_left and min_right using the sentinel values and return based on parity of m+n. Time: O(log min(m,n)), space: O(1).

The Java implementation follows the same structure using int left1 = (i > 0) ? nums1[i-1] : Integer.MIN_VALUE and int right1 = (i < m) ? nums1[i] : Integer.MAX_VALUE with equivalent expressions for left2 and right2. The while loop condition is lo <= hi and the return statement uses (double)(maxLeft + minRight) / 2 for even totals. Java's integer arithmetic requires the cast to double to avoid truncation. The ArrayDeque-based BFS pattern from grid problems does not apply here — this is a pure mathematical binary search with no data structures beyond primitive variables.

Common implementation mistakes: (1) not swapping arrays to ensure m <= n, which causes j to go negative; (2) using half = (m + n) // 2 instead of (m + n + 1) // 2, which breaks the odd-length case; (3) not using sentinels for boundary partitions, causing index-out-of-bounds; (4) integer overflow in Java when computing (maxLeft + minRight) without casting to long or double first if values can be near Integer.MAX_VALUE.

Find Median from Data Stream (LeetCode 295) solves a different but related problem: maintaining a running median as numbers are added one by one. It uses two heaps — a max-heap for the lower half and a min-heap for the upper half — to keep the median accessible in O(1) time with O(log n) insertions. Understanding the partition-based median from LeetCode 4 deepens your intuition for why splitting the data into balanced halves is the right approach for median problems.

Search in Rotated Sorted Array (LeetCode 33) and Kth Smallest Element in a Sorted Matrix (LeetCode 378) are close relatives in the binary search family. LeetCode 33 applies binary search to an array that has been rotated, requiring careful case analysis in each iteration. LeetCode 378 uses binary search on the answer space — binary searching on the value rather than the index — which is a powerful technique that generalizes to many "find the k-th" problems. Median of Two Sorted Arrays bridges index-based and value-based binary search thinking.

The broader binary search patterns guide covers the canonical templates: find leftmost/rightmost position, binary search on answer, binary search with predicate functions. LeetCode 4 is the crown jewel of index-based binary search problems because the "predicate" — the partition validity condition — is two-dimensional (involves both arrays simultaneously), which is unusual and intellectually satisfying. Mastering this problem gives you a strong foundation for any binary search problem that appears in senior engineering interviews.