Median of Two Sorted Arrays is the #20 most asked LeetCode problem globally — and the hardest HARD problem in the top 20. It's the ultimate test of binary search mastery.
Our analysis of 10,385 verified interview questions across 259 companies shows it appeared 59 times across 21 companies — including Google, Amazon, Meta, Microsoft, Goldman Sachs, Citadel, Bloomberg, DE Shaw, LinkedIn, and Dropbox.
The O(m+n) merge approach is obvious. The challenge — and what interviewers specifically test — is the O(log(min(m,n))) binary search on partition. The idea: binary search for the correct partition point in the smaller array such that the left halves of both arrays contain exactly half of all elements. This is genuinely difficult; understand the logic deeply, not just the code.
| Metric | Value |
|---|---|
| Total Interview Appearances | 59 verified mentions |
| Companies That Ask It | 21 companies |
| Global Rank | #20 out of 10,385 questions |
| Difficulty | Hard |
| Core Patterns | Array, Binary Search, Divide and Conquer |
Google, Amazon, Meta, Microsoft, Goldman Sachs, Citadel, Bloomberg, DE Shaw, LinkedIn, Dropbox, Adobe, Akamai, Apple, Autodesk, Capgemini, Cognizant, Flipkart, IBM, Infosys, Intuit, and 1 more.
LeetCode #4 — Median of Two Sorted Arrays
Given two sorted arrays nums1 and nums2 of size m and n, return the median of the two sorted arrays. The overall run time complexity should be O(log(m+n)).
Input: nums1 = [1,3], nums2 = [2] → Output: 2.0
Input: nums1 = [1,2], nums2 = [3,4] → Output: 2.5
Input: nums1 = [0,0], nums2 = [0,0] → Output: 0.0
Input: nums1 = [], nums2 = [1] → Output: 1.0Merge both arrays using the merge step from merge sort, find the middle element(s). This is O(m+n) time and space. Always mention this first in an interview before presenting the optimal solution.
The median divides the combined array into two equal halves. We need to find a partition of nums1 (taking i elements from the left) and a corresponding partition of nums2 (taking j elements from the left) such that:
i + j = (m + n + 1) / 2 — left halves together contain exactly half the elements.nums1[i-1] <= nums2[j] — max of left side of nums1 ≤ min of right side of nums2.nums2[j-1] <= nums1[i] — max of left side of nums2 ≤ min of right side of nums1.Binary search for i on the smaller array. When conditions are satisfied, compute the median from the four boundary elements.
Always run binary search on the shorter array (length m). This gives O(log(min(m,n))) complexity. Once i is fixed, j is determined by the half-split formula — no nested search needed.
nums1 is the shorter array (swap if needed).left=0, right=m. Binary search for partition i in nums1.j = half - i where half = (m+n+1)//2.maxLeft1, minRight1, maxLeft2, minRight2 (use -inf/+inf for out-of-bounds).maxLeft1 <= minRight2 and maxLeft2 <= minRight1 → correct partition. Compute median.maxLeft1 > minRight2 → move i left (right = i-1). Else move i right (left = i+1).def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:
# Ensure nums1 is the smaller array
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
half = (m + n + 1) // 2
left, right = 0, m
while left <= right:
i = (left + right) // 2 # partition in nums1
j = half - i # partition in nums2
# Boundary values (use -inf/+inf for edges)
maxLeft1 = float('-inf') if i == 0 else nums1[i - 1]
minRight1 = float('inf') if i == m else nums1[i]
maxLeft2 = float('-inf') if j == 0 else nums2[j - 1]
minRight2 = float('inf') if j == n else nums2[j]
if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
# Correct partition found
if (m + n) % 2 == 1:
return float(max(maxLeft1, maxLeft2))
else:
return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0
elif maxLeft1 > minRight2:
right = i - 1 # move i left
else:
left = i + 1 # move i rightclass Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
int[] temp = nums1; nums1 = nums2; nums2 = temp;
}
int m = nums1.length, n = nums2.length;
int half = (m + n + 1) / 2;
int left = 0, right = m;
while (left <= right) {
int i = (left + right) / 2;
int j = half - i;
int maxLeft1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
int minRight1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
int maxLeft2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
int minRight2 = (j == n) ? Integer.MAX_VALUE : nums2[j];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
if ((m + n) % 2 == 1)
return Math.max(maxLeft1, maxLeft2);
return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;
} else if (maxLeft1 > minRight2) {
right = i - 1;
} else {
left = i + 1;
}
}
return 0.0;
}
}var findMedianSortedArrays = function(nums1, nums2) {
if (nums1.length > nums2.length)
[nums1, nums2] = [nums2, nums1];
const m = nums1.length, n = nums2.length;
const half = Math.floor((m + n + 1) / 2);
let left = 0, right = m;
while (left <= right) {
const i = Math.floor((left + right) / 2);
const j = half - i;
const maxLeft1 = i === 0 ? -Infinity : nums1[i - 1];
const minRight1 = i === m ? Infinity : nums1[i];
const maxLeft2 = j === 0 ? -Infinity : nums2[j - 1];
const minRight2 = j === n ? Infinity : nums2[j];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
if ((m + n) % 2 === 1)
return Math.max(maxLeft1, maxLeft2);
return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;
} else if (maxLeft1 > minRight2) {
right = i - 1;
} else {
left = i + 1;
}
}
};| Approach | Time | Space |
|---|---|---|
| Merge + Find Middle | O(m+n) | O(m+n) |
| Binary Search on Partition | O(log(min(m,n))) | O(1) |
[1,3] + [2,4]. Draw the left/right halves. Then code it.i==0, i==m).maxLeft1 <= minRight2 and maxLeft2 <= minRight1) verbally before coding.Always present the O(m+n) merge approach first. Then say "but we can do better — O(log(min(m,n))) using binary search on the partition." This shows you understand the solution progression and won't panic if you can't immediately recall the O(log n) version under pressure.
Tag on DSAPrep.dev under Binary Search and Divide and Conquer.