How to Solve Median of Two Sorted Arrays on LeetCode
The Median of Two Sorted Arrays is one of the hardest and most famous LeetCode interview problems. It tests your knowledge of binary search, array partitioning, and efficient problem solving.
Problem Statement
Given two sorted arrays
nums1andnums2of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Example:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.0
Explanation: The merged array is [1,2,3] and the median is 2.0.
Why This Problem Matters for Interviews
This problem:
- Evaluates advanced use of binary search
- Assesses your ability to optimize for logarithmic time
- Requires careful handling of edge cases and partitioning
Optimal Approach: Binary Search Partition
Binary Search on the Smaller Array
Partition both arrays so that all elements on the left are less than or equal to all elements on the right.
Time Complexity: O(log(min(m, n)))
Space Complexity: O(1)
def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:
A, B = nums1, nums2
if len(A) > len(B):
A, B = B, A
m, n = len(A), len(B)
total = m + n
half = total // 2
l, r = 0, m
while l <= r:
i = (l + r) // 2
j = half - i
Aleft = A[i-1] if i > 0 else float('-inf')
Aright = A[i] if i < m else float('inf')
Bleft = B[j-1] if j > 0 else float('-inf')
Bright = B[j] if j < n else float('inf')
if Aleft <= Bright and Bleft <= Aright:
if total % 2:
return min(Aright, Bright)
return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
elif Aleft > Bright:
r = i - 1
else:
l = i + 1
Key Interview Talking Points
- Why brute force merge is O(m+n) and not optimal.
- How binary search is used to achieve O(log(min(m, n))).
- How to handle even/odd length and empty arrays.
- The importance of partition correctness and edge conditions.
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force Merge | O(m+n) | O(m+n) |
| Binary Search | O(log(min(m, n))) | O(1) |
Pro Interview Tips
- Draw diagrams to show partitioning during interviews.
- Explain your code for both even and odd total lengths.
- Practice with test cases