Median of Two Sorted Arrays
Problem
Given two sorted arrays nums1 and nums2, return the median of the two sorted arrays combined. The overall run time complexity should be O(log (m+n)).
- nums1.length == m
- nums2.length == n
- 0 ≤ m, n ≤ 1000
- 1 ≤ m + n ≤ 2000
- −10⁶ ≤ nums1[i], nums2[i] ≤ 10⁶
Example
nums1 = [1, 3], nums2 = [2]2.0The combined sorted array is [1, 2, 3]. The median is the middle element 2. The algorithm uses binary search on the smaller array to find a partition such that all elements on the left side of the partition are less than or equal to all elements on the right side. It calculates indices i and j to partition nums1 and nums2 respectively. By comparing boundary elements around the partitions, it adjusts the search space until the correct partition is found. Then, depending on the total length parity, it returns either the minimum of the right partition elements or the average of the max left and min right elements.
Approach
Straightforward Solution
A naive approach merges the two arrays and then finds the median, which takes O(m+n) time and space. This is inefficient for large inputs and does not meet the O(log(m+n)) time requirement.
Core Observation
The median splits the combined sorted array into two halves of equal length (or nearly equal if odd). The key is to find a partition between the two arrays such that all elements on the left are less than or equal to all elements on the right.
Path to Optimal
The problem's O(log(m+n)) time constraint signals a binary search approach. By always binary searching the smaller array, the algorithm tries to find an index i that partitions nums1 and an index j that partitions nums2 such that the left partition max elements are less than or equal to the right partition min elements. This transforms the problem into a search for the correct partition point, which can be found in O(log(min(m,n))) time.
Optimal Approach
Use binary search on the smaller array to find the partition index i. Calculate j = half - i - 2 to partition the second array accordingly. Compare boundary elements Aleft, Aright, Bleft, Bright to check if the partition is valid. If valid, compute the median based on total length parity. Otherwise, adjust the binary search range by moving left or right pointers. This approach guarantees logarithmic time complexity and constant space.
Time
O(log(min(m, n)))
The binary search is performed on the smaller array, which has length min(m, n). Each iteration halves the search space, leading to logarithmic time complexity.
Space
O(1)
Only a fixed number of variables are used for indices and boundary values, with no additional data structures proportional to input size.
Pattern Spotlight
Modified Binary Search (Partitioning Technique)
When searching for a median or kth element across two sorted arrays, transform the problem into finding a partition point that balances elements on both sides, then use binary search on the smaller array to efficiently locate this partition.
Solution
| 1 | class Solution:
|
| 2 | def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
|
| 3 | A, B = nums1, nums2
|
| 4 | total = len(nums1) + len(nums2)
|
| 5 | half = total // 2
|
| 6 |
|
| 7 | if len(B) < len(A):
|
| 8 | A, B = B, A
|
| 9 |
|
| 10 | l, r = 0, len(A) - 1
|
| 11 | while True:
|
| 12 | i = (l + r) // 2
|
| 13 | j = half - i - 2
|
| 14 |
|
| 15 | Aleft = A[i] if i >= 0 else float("-infinity")
|
| 16 | Aright = A[i + 1] if (i + 1) < len(A) else float("infinity")
|
| 17 | Bleft = B[j] if j >= 0 else float("-infinity")
|
| 18 | Bright = B[j + 1] if (j + 1) < len(B) else float("infinity")
|
| 19 |
|
| 20 | if Aleft <= Bright and Bleft <= Aright:
|
| 21 | if total % 2:
|
| 22 | return min(Aright, Bright)
|
| 23 | return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
|
| 24 | elif Aleft > Bright:
|
| 25 | r = i - 1
|
| 26 | else:
|
| 27 | l = i + 1 |
| 1 | class Solution { |
| 2 | public double findMedianSortedArrays(int[] nums1, int[] nums2) { |
| 3 | int[] A = nums1; |
| 4 | int[] B = nums2; |
| 5 | int total = nums1.length + nums2.length; |
| 6 | int half = total / 2; |
| 7 | |
| 8 | if (B.length < A.length) { |
| 9 | int[] temp = A; |
| 10 | A = B; |
| 11 | B = temp; |
| 12 | } |
| 13 | |
| 14 | int l = 0; |
| 15 | int r = A.length - 1; |
| 16 | |
| 17 | while (true) { |
| 18 | int i = l + (r - l) / 2; |
| 19 | int j = half - i - 2; |
| 20 | |
| 21 | double Aleft = i >= 0 ? A[i] : Double.NEGATIVE_INFINITY; |
| 22 | double Aright = (i + 1) < A.length ? A[i + 1] : Double.POSITIVE_INFINITY; |
| 23 | double Bleft = j >= 0 ? B[j] : Double.NEGATIVE_INFINITY; |
| 24 | double Bright = (j + 1) < B.length ? B[j + 1] : Double.POSITIVE_INFINITY; |
| 25 | |
| 26 | if (Aleft <= Bright && Bleft <= Aright) { |
| 27 | if (total % 2 == 1) { |
| 28 | return Math.min(Aright, Bright); |
| 29 | } |
| 30 | return (Math.max(Aleft, Bleft) + Math.min(Aright, Bright)) / 2.0; |
| 31 | } else if (Aleft > Bright) { |
| 32 | r = i - 1; |
| 33 | } else { |
| 34 | l = i + 1; |
| 35 | } |
| 36 | } |
| 37 | } |
| 38 | } |
Step-by-Step Solution
Ensure Binary Search on the Smaller Array to Minimize Search Space
| 3 | A, B = nums1, nums2
|
| 7 | if len(B) < len(A):
|
| 8 | A, B = B, A
|
Objective
To guarantee the binary search is performed on the smaller array, reducing complexity and simplifying boundary conditions.
Key Insight
By swapping the arrays if the second is smaller, the algorithm ensures the binary search operates on the smaller array. This prevents out-of-bound partition indices and keeps the search space minimal, which is critical for achieving O(log(min(m,n))) time complexity.
Interview Quick-Check
Core Logic
Swapping arrays ensures the binary search is always on the smaller array, which bounds the search space and simplifies partition calculations.
Common Pitfalls & Bugs
Failing to swap can cause invalid partition indices and complicate boundary checks, leading to incorrect results or runtime errors.
Perform Binary Search to Find Correct Partition Indices
| 4 | total = len(nums1) + len(nums2)
|
| 5 | half = total // 2
|
| 10 | l, r = 0, len(A) - 1
|
| 11 | while True:
|
| 12 | i = (l + r) // 2
|
| 13 | j = half - i - 2
|
| 15 | Aleft = A[i] if i >= 0 else float("-infinity")
|
| 16 | Aright = A[i + 1] if (i + 1) < len(A) else float("infinity")
|
| 17 | Bleft = B[j] if j >= 0 else float("-infinity")
|
| 18 | Bright = B[j + 1] if (j + 1) < len(B) else float("infinity")
|
| 24 | elif Aleft > Bright:
|
| 25 | r = i - 1
|
| 26 | else:
|
| 27 | l = i + 1 |
Objective
To locate partition indices i and j such that all elements on the left are less than or equal to those on the right.
Key Insight
The binary search iteratively adjusts the partition index i in the smaller array. The corresponding partition index j in the other array is derived from the total half length. By comparing boundary elements around the partitions, the algorithm decides whether to move left or right, converging on the correct partition that balances the combined arrays.
Interview Quick-Check
Core Logic
Calculate partition indices i and j so that left partitions contain half the total elements; adjust i based on comparisons of Aleft, Aright, Bleft, and Bright to maintain the partition invariant.
State & Boundaries
Use -infinity and infinity for out-of-bound indices to handle edge partitions gracefully.
Common Pitfalls & Bugs
Incorrect calculation of j or improper boundary checks can cause infinite loops or incorrect median calculation.
Calculate and Return Median Based on Partition Validity and Total Length Parity
| 20 | if Aleft <= Bright and Bleft <= Aright:
|
| 21 | if total % 2:
|
| 22 | return min(Aright, Bright)
|
| 23 | return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
|
Objective
To compute the median once the correct partition is found, considering whether the total length is odd or even.
Key Insight
If the partition is valid (Aleft <= Bright and Bleft <= Aright), the median depends on the parity of the total length. For odd length, the median is the minimum of the right partition elements. For even length, it is the average of the maximum left partition element and the minimum right partition element. This calculation leverages the partitioning to directly access median candidates without merging arrays.
Interview Quick-Check
Core Logic
Use the partition boundary elements to compute the median directly, avoiding full merge and achieving O(1) median calculation after partitioning.
State & Boundaries
Handle odd and even total lengths separately to correctly compute the median.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
if Aleft <= Bright and Bleft <= Aright:Check whether the current partition is valid.
This is the core correctness test: the partition is valid only when every left-side boundary is less than or equal to the opposite right-side boundary.
if len(B) < len(A):Check whether the arrays should be swapped so A is the smaller array.
Binary searching the smaller array keeps the search space minimal and prevents awkward partition bounds.
return (max(Aleft, Bleft) + min(Aright, Bright)) / 2Return the even-length median.
For an even total length, the median is the average of the largest left-side value and the smallest right-side value.
elif Aleft > Bright:Check whether the partition in A is too far right.
If A's left boundary is too large, the partition in A is too far right and must move left.
A, B = B, ASwap A and B.
Completing the swap preserves the invariant that A is the array being binary searched.
i = (l + r) // 2Compute the partition index i in A.
The midpoint index chooses the current partition location in A.
j = half - i - 2Compute the matching partition index j in B.
The partition index in B must complement i so the total number of left-side elements equals half.
return min(Aright, Bright)Return the odd-length median.
For an odd total length, the median is the first value on the right side of the valid partition.
else:Enter the branch where the partition must move right.
If the previous failure case does not apply, the partition in A must be too far left.
Aleft = A[i] if i >= 0 else float("-infinity")Read the left boundary value of A, using -infinity when needed.
Using negative infinity for out-of-bounds left values lets the same comparison logic work at the array edge.
Aright = A[i + 1] if (i + 1) < len(A) else float("infinity")Read the right boundary value of A, using infinity when needed.
Using positive infinity for out-of-bounds right values lets the same comparison logic work at the array edge.
Bleft = B[j] if j >= 0 else float("-infinity")Read the left boundary value of B, using -infinity when needed.
This mirrors the boundary handling for the second array's left partition edge.
Bright = B[j + 1] if (j + 1) < len(B) else float("infinity")Read the right boundary value of B, using infinity when needed.
This mirrors the boundary handling for the second array's right partition edge.
if total % 2:Check whether the combined length is odd.
Once the partition is valid, the median formula depends on whether the total length is odd or even.
r = i - 1Move the right search boundary leftward.
Shrinking the right boundary moves the partition left on the next iteration.
l = i + 1Move the left search boundary rightward.
Increasing the left boundary moves the partition right on the next iteration.
half = total // 2Compute the target left-partition size.
The partition must place half the total elements on the left side, so this value drives the index relationship between the two arrays.
while True:Begin the partition-search loop.
The search continues until a valid partition is found; each iteration moves one of the boundaries toward that partition.
l, r = 0, len(A) - 1Initialize the binary-search boundaries in A.
These pointers define the binary-search interval over the smaller array's partition index.
total = len(nums1) + len(nums2)Compute the total number of elements across both arrays.
The total combined length determines whether the median is a single middle element or an average of two middle elements.
A, B = nums1, nums2Assign the input arrays to A and B.
Using A and B as aliases simplifies the later swap and partition logic.
Test Your Understanding
Why is it necessary to always binary search the smaller array instead of the larger one?
Because the binary search partitions the smaller array, ensuring the search space is minimized and the calculated partition index in the other array is valid. Searching the larger array could lead to invalid partition indices and complicate boundary conditions.
Related Problems
Binary Search pattern
Don't just read it. Drill it.
Reconstruct Median of Two Sorted Arrays from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Median of Two Sorted Arrays drill