69. Median of Two Sorted Arrays
🔗 LeetCode Problem: 4. Median of Two Sorted Arrays
📊 Difficulty: Hard
🏷️ Topics: Array, Binary Search, Divide and Conquer
Problem Statement
Given two sorted arrays nums1 and nums2 of 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 1:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Constraints:
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -10^6 <= nums1[i], nums2[i] <= 10^6
🎨 Visual Understanding
The Problem Visualized
Example 1: nums1 = [1,3], nums2 = [2]
Merged (conceptually): [1, 2, 3]
↑
median = 2
Total elements: 3 (odd)
Median: middle element = element at index 1
Example 2: nums1 = [1,2], nums2 = [3,4]
Merged (conceptually): [1, 2, 3, 4]
↑ ↑
median = (2 + 3) / 2 = 2.5
Total elements: 4 (even)
Median: average of two middle elements
Larger example: nums1 = [1,3,8,9,15], nums2 = [7,11,18,19,21,25]
Merged: [1, 3, 7, 8, 9, 11, 15, 18, 19, 21, 25]
↑
median = 11
Total: 11 elements (odd)
Median: element at index 5
The Partition Concept (KEY!)
The KEY insight: We don't need to merge! We need to PARTITION!
nums1 = [1, 3, 8, 9, 15]
nums2 = [7, 11, 18, 19, 21, 25]
Goal: Partition both arrays such that:
- Left half has (m + n + 1) / 2 elements
- All elements in left half ≤ all elements in right half
Visual partition:
nums1: [1, 3, 8 | 9, 15] left1: [1,3,8], right1: [9,15]
nums2: [7, 11 | 18, 19, 21, 25] left2: [7,11], right2: [18,19,21,25]
Left half: [1, 3, 8, 7, 11] → 5 elements
Right half: [9, 15, 18, 19, 21, 25] → 6 elements
Check: max(left) ≤ min(right)?
max(left) = max(8, 11) = 11
min(right) = min(9, 18) = 9
11 > 9 ✗ Invalid partition!
Try different partition...
nums1: [1, 3 | 8, 9, 15]
nums2: [7, 11, 18 | 19, 21, 25]
Left half: [1, 3, 7, 11, 18] → 5 elements
Right half: [8, 9, 15, 19, 21, 25] → 6 elements
Check: max(left) ≤ min(right)?
max(left) = max(3, 18) = 18
min(right) = min(8, 19) = 8
18 > 8 ✗ Invalid!
Correct partition:
nums1: [1, 3, 8, 9 | 15]
nums2: [7 | 11, 18, 19, 21, 25]
Left half: [1, 3, 8, 9, 7] → 5 elements
Right half: [15, 11, 18, 19, 21, 25] → 6 elements
Check: max(left) ≤ min(right)?
max(left) = max(9, 7) = 9
min(right) = min(15, 11) = 11
9 ≤ 11 ✓ Valid!
Median = max(left) = 11 ✓
🚨 CRITICAL INSIGHT - Binary Search on Partition!
The Key Pattern!
We're NOT searching for a VALUE!
We're searching for a PARTITION POINT!
What to partition?
The SMALLER array (for efficiency)
Search space:
Partition position in smaller array: [0, m]
where m = length of smaller array
How to determine partition2?
If partition1 is known:
partition2 = (m + n + 1) / 2 - partition1
This ensures left half has correct size!
Valid partition conditions:
1. left1 ≤ right2 (maxLeft1 ≤ minRight2)
2. left2 ≤ right1 (maxLeft2 ≤ minRight1)
If both true: We found the median!
If left1 > right2:
partition1 too large, search left
If left2 > right1:
partition1 too small, search right
🧠 INTUITION: Why Left Half Needs (m+n+1)/2 Elements
This is the MOST confusing part! Let's build intuition step by step:
STEP 1: What is a median?
════════════════════════════════════════════════════════════════
For a SINGLE sorted array:
Odd length (e.g., 7 elements):
[1, 2, 3, 4, 5, 6, 7]
↑
median = 4 (the middle element)
Left side: [1, 2, 3] → 3 elements
Middle: 4
Right side: [5, 6, 7] → 3 elements
Notice: Left has same count as right!
Even length (e.g., 8 elements):
[1, 2, 3, 4, 5, 6, 7, 8]
↑ ↑
median = (4 + 5) / 2 = 4.5
Left side: [1, 2, 3, 4] → 4 elements
Right side: [5, 6, 7, 8] → 4 elements
Notice: Left has same count as right!
Key observation: For median, we need to SPLIT the array
such that left half ≈ right half in size!
STEP 2: What about TWO arrays?
════════════════════════════════════════════════════════════════
If we MERGE two sorted arrays, we get ONE sorted array:
nums1 = [1, 3, 8, 9, 15]
nums2 = [7, 11, 18, 19, 21, 25]
Merged = [1, 3, 7, 8, 9, 11, 15, 18, 19, 21, 25]
↑
median = 11
Total = 11 (odd)
Left side needs: 5 elements
Right side has: 6 elements
The insight: We don't actually need to merge!
We just need to PARTITION both arrays such that:
- Combined left half has 5 elements
- Combined right half has 6 elements
- All left ≤ all right
STEP 3: How many elements should left half have?
════════════════════════════════════════════════════════════════
Total elements: m + n
For ODD total (e.g., 11):
Median is the MIDDLE element
Middle position: (11 + 1) / 2 = 6th position (1-indexed)
OR: 11 / 2 = 5 (0-indexed)
We want: Left has 5, Right has 6
OR think: Left has ONE LESS than right
Formula: left_size = (m + n + 1) / 2 = (11 + 1) / 2 = 6
Wait, that gives 6, not 5!
In 0-indexed terms:
Left indices: [0, 1, 2, 3, 4, 5] → 6 elements
This INCLUDES the median position!
The median is the LAST element of left half!
median = max(left_half)
For EVEN total (e.g., 10):
Median is AVERAGE of two middle elements
Middle positions: 5th and 6th (1-indexed)
OR: indices 4 and 5 (0-indexed)
We want: Left has 5, Right has 5
Equal split!
Formula: left_size = (m + n + 1) / 2 = (10 + 1) / 2 = 5
The median is average of:
Last element of left: max(left_half)
First element of right: min(right_half)
median = (max(left) + min(right)) / 2
The magic: (m + n + 1) / 2 works for BOTH cases!
STEP 4: The "+1" trick - why does it work?
════════════════════════════════════════════════════════════════
Let's see the formula in action:
ODD total (11):
Without +1: 11 / 2 = 5
With +1: (11 + 1) / 2 = 6 ✓
We want left to have 6 elements (includes median)
The +1 gives us the correct size!
EVEN total (10):
Without +1: 10 / 2 = 5 ✓
With +1: (10 + 1) / 2 = 5 ✓
We want left to have 5 elements
Both work, but +1 doesn't break it!
ODD total (7):
Without +1: 7 / 2 = 3 ✗ (Wrong! Should be 4)
With +1: (7 + 1) / 2 = 4 ✓
We want left to have 4 elements (includes median)
Only +1 gives correct size!
The "+1" fixes ODD case without breaking EVEN case!
In integer division:
(odd + 1) / 2 → rounds up to include median
(even + 1) / 2 → still gives exact half
STEP 5: Visual proof with examples
════════════════════════════════════════════════════════════════
Example 1: Total = 11 (ODD)
Merged array (conceptual):
[1, 3, 7, 8, 9, 11, 15, 18, 19, 21, 25]
0 1 2 3 4 5 6 7 8 9 10
Indices 0-10, total 11 elements
Left half: indices [0, 1, 2, 3, 4, 5] → 6 elements
Right half: indices [6, 7, 8, 9, 10] → 5 elements
Median = element at index 5 = 11
= Last element of left half
= max(left_half)
Left size = (11 + 1) / 2 = 6 ✓
Example 2: Total = 10 (EVEN)
Merged array (conceptual):
[1, 3, 7, 8, 9, 11, 15, 18, 19, 21]
0 1 2 3 4 5 6 7 8 9
Left half: indices [0, 1, 2, 3, 4] → 5 elements
Right half: indices [5, 6, 7, 8, 9] → 5 elements
Median = (element[4] + element[5]) / 2
= (9 + 11) / 2 = 10
= (max(left) + min(right)) / 2
Left size = (10 + 1) / 2 = 5 ✓
The formula works perfectly for both!
STEP 6: Why not (m + n) / 2?
════════════════════════════════════════════════════════════════
Let's test WITHOUT the +1:
ODD total (11):
Left size = 11 / 2 = 5
Right size = 11 - 5 = 6
[1, 3, 7, 8, 9, | 11, 15, 18, 19, 21, 25]
← 5 elements | ← 6 elements →
Where's the median?
Median should be element at index 5 (11)
But our left only goes to index 4 (9)
We MISSED the median! ✗
EVEN total (10):
Left size = 10 / 2 = 5 ✓
Right size = 10 - 5 = 5 ✓
Works fine for even!
The problem: Without +1, we lose the median in ODD case!
STEP 7: Putting it all together
════════════════════════════════════════════════════════════════
When we partition two arrays:
nums1: [a, b, c, | d, e] partition1 = 3 (3 elements in left)
nums2: [f, g, | h, i, j] partition2 = 2 (2 elements in left)
Combined left: [a, b, c, f, g] → 5 elements
Combined right: [d, e, h, i, j] → 5 elements
For this to be a valid partition:
Total elements = m + n = 10
Left needs: (10 + 1) / 2 = 5 ✓
If partition1 = 3:
partition2 = 5 - 3 = 2 ✓
The formula ensures:
partition1 + partition2 = (m + n + 1) / 2
This gives us the correct median!
The Partition Formula
Total elements: m + n
Left half size: (m + n + 1) / 2
Why this size?
- For ODD total: Includes the median element
- For EVEN total: Exact half split
- The +1 handles both cases correctly!
If we partition array1 at position p1:
Left from array1: p1 elements
We need from array2:
Left from array2: (m + n + 1) / 2 - p1 elements
So: partition2 = (m + n + 1) / 2 - partition1
Example:
m = 5, n = 6, total = 11
Left half needs: (11 + 1) / 2 = 6 elements
If partition1 = 4 (4 elements from nums1):
partition2 = 6 - 4 = 2 (2 elements from nums2)
Total in left: 4 + 2 = 6 ✓
This ensures left half has exactly 6 elements,
which includes the median position for odd total!
Finding the Median from Partition
Once we have valid partition:
nums1: [...left1... | ...right1...]
↑ maxLeft1 minRight1 ↑
nums2: [...left2... | ...right2...]
↑ maxLeft2 minRight2 ↑
If total is ODD:
median = max(maxLeft1, maxLeft2)
If total is EVEN:
median = (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0
Why?
max of left halves = largest in left
min of right halves = smallest in right
For even: average of these two middle elements
🎯 Approach 1: Merge and Find Median (Brute Force)
The Most Natural Thinking 💭
Core Logic:
Merge both arrays
Find median in merged array
Implementation
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int[] merged = new int[m + n];
// Merge two sorted arrays
int i = 0, j = 0, k = 0;
while (i < m && j < n) {
if (nums1[i] < nums2[j]) {
merged[k++] = nums1[i++];
} else {
merged[k++] = nums2[j++];
}
}
while (i < m) {
merged[k++] = nums1[i++];
}
while (j < n) {
merged[k++] = nums2[j++];
}
// Find median
int total = m + n;
if (total % 2 == 1) {
return merged[total / 2];
} else {
return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
}
}
⏰ Time: O(m + n) - Merge both arrays
💾 Space: O(m + n) - Store merged array
❌ Problem: Doesn't meet O(log(m+n)) requirement!
🎯 Approach 2: Binary Search on Partition (Optimal) ⭐
Better Approach 💡
🧠 The Core Insight
Don't merge! Find the partition!
Binary search on partition position in smaller array
Calculate corresponding partition in larger array
Check if partition is valid
Adjust based on comparison
The Strategy:
Binary Search on Partition:
1. Ensure nums1 is smaller (swap if needed)
2. Binary search on partition position in nums1
3. For each partition1, calculate partition2
4. Check partition validity:
- Compare maxLeft1 with minRight2
- Compare maxLeft2 with minRight1
5. Adjust search based on comparison
6. When found, calculate median
Implementation
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// Ensure nums1 is the smaller array
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.length;
int n = nums2.length;
int left = 0, right = m;
while (left <= right) {
// Partition positions
int partition1 = (left + right) / 2;
int partition2 = (m + n + 1) / 2 - partition1;
// Handle edge cases for partition boundaries
int maxLeft1 = (partition1 == 0) ? Integer.MIN_VALUE : nums1[partition1 - 1];
int minRight1 = (partition1 == m) ? Integer.MAX_VALUE : nums1[partition1];
int maxLeft2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2[partition2 - 1];
int minRight2 = (partition2 == n) ? Integer.MAX_VALUE : nums2[partition2];
// Check if partition is valid
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
// Found the correct partition!
// Calculate median based on odd/even total
if ((m + n) % 2 == 0) {
// Even: average of two middle elements
return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;
} else {
// Odd: max of left halves
return Math.max(maxLeft1, maxLeft2);
}
} else if (maxLeft1 > minRight2) {
// partition1 is too large, search left
right = partition1 - 1;
} else {
// partition1 is too small, search right
left = partition1 + 1;
}
}
throw new IllegalArgumentException("Input arrays are not sorted");
}
⏰ Time: O(log(min(m, n))) - Binary search on smaller array
💾 Space: O(1) - Only variables
🔍 Dry Run
Example: nums1 = [1,3,8,9,15], nums2 = [7,11,18,19,21,25]
Goal: Find median
nums1 is smaller (5 < 6), so search in nums1
m = 5, n = 6, total = 11 (odd)
Initial: left = 0, right = 5
Iteration 1:
partition1 = (0 + 5) / 2 = 2
partition2 = (5 + 6 + 1) / 2 - 2 = 6 - 2 = 4
nums1: [1, 3 | 8, 9, 15] partition at 2
nums2: [7, 11, 18, 19 | 21, 25] partition at 4
maxLeft1 = nums1[1] = 3
minRight1 = nums1[2] = 8
maxLeft2 = nums2[3] = 19
minRight2 = nums2[4] = 21
Check: maxLeft1 ≤ minRight2 AND maxLeft2 ≤ minRight1?
3 ≤ 21? ✓
19 ≤ 8? ✗
maxLeft2 > minRight1
partition1 too small, search right
left = 3
Iteration 2:
partition1 = (3 + 5) / 2 = 4
partition2 = 6 - 4 = 2
nums1: [1, 3, 8, 9 | 15] partition at 4
nums2: [7, 11 | 18, 19, 21, 25] partition at 2
maxLeft1 = nums1[3] = 9
minRight1 = nums1[4] = 15
maxLeft2 = nums2[1] = 11
minRight2 = nums2[2] = 18
Check: maxLeft1 ≤ minRight2 AND maxLeft2 ≤ minRight1?
9 ≤ 18? ✓
11 ≤ 15? ✓
Valid partition found! ✓
Total is odd (11):
median = max(maxLeft1, maxLeft2)
= max(9, 11)
= 11 ✓
Example: nums1 = [1,2], nums2 = [3,4]
m = 2, n = 2, total = 4 (even)
Initial: left = 0, right = 2
Iteration 1:
partition1 = 1
partition2 = (2 + 2 + 1) / 2 - 1 = 2 - 1 = 1
nums1: [1 | 2] partition at 1
nums2: [3 | 4] partition at 1
maxLeft1 = nums1[0] = 1
minRight1 = nums1[1] = 2
maxLeft2 = nums2[0] = 3
minRight2 = nums2[1] = 4
Check: 1 ≤ 4? ✓, 3 ≤ 2? ✗
maxLeft2 > minRight1
partition1 too small, search right
left = 2
Iteration 2:
partition1 = 2
partition2 = 2 - 2 = 0
nums1: [1, 2 |] partition at 2 (end)
nums2: [| 3, 4] partition at 0 (start)
maxLeft1 = nums1[1] = 2
minRight1 = Integer.MAX_VALUE (no right in nums1)
maxLeft2 = Integer.MIN_VALUE (no left in nums2)
minRight2 = nums2[0] = 3
Check: 2 ≤ 3? ✓, MIN_VALUE ≤ MAX_VALUE? ✓
Valid! ✓
Total is even (4):
median = (max(2, MIN_VALUE) + min(MAX_VALUE, 3)) / 2.0
= (2 + 3) / 2.0
= 2.5 ✓
🎯 Why This Works - Deep Dive
The Partition Concept:
═══════════════════════════════════════════════════════════════
Instead of merging, we partition both arrays:
nums1: [...left1... | ...right1...]
nums2: [...left2... | ...right2...]
Combined:
Left half: left1 + left2
Right half: right1 + right2
For valid partition:
- Size of left half = (m + n + 1) / 2
- All left ≤ all right
The "+1" in formula:
Works for both odd and even totals!
Odd (e.g., 7): (7 + 1) / 2 = 4 (left has 4, right has 3)
Even (e.g., 8): (8 + 1) / 2 = 4 (left has 4, right has 4)
Why Search Smaller Array:
═══════════════════════════════════════════════════════════════
Binary search complexity: O(log m)
If we search the smaller array:
Time: O(log(min(m, n)))
If we search the larger:
Time: O(log(max(m, n)))
Always better to search smaller!
Also: Ensures partition2 is always valid
partition2 = (m + n + 1) / 2 - partition1
If partition1 can be [0, m] and m ≤ n:
partition2 = [halfLen, halfLen - m]
This stays in range [0, n] ✓
The Partition Validity Check:
═══════════════════════════════════════════════════════════════
Valid partition means:
maxLeft1 ≤ minRight2 (elements in left1 ≤ right2)
maxLeft2 ≤ minRight1 (elements in left2 ≤ right1)
If maxLeft1 > minRight2:
partition1 is too far right
Move it left: right = partition1 - 1
If maxLeft2 > minRight1:
partition1 is too far left
Move it right: left = partition1 + 1
Edge Cases with MIN/MAX:
═══════════════════════════════════════════════════════════════
When partition is at boundary:
partition1 = 0: No left1, use MIN_VALUE
partition1 = m: No right1, use MAX_VALUE
Why MIN/MAX works:
MIN_VALUE is smaller than everything → always valid in left
MAX_VALUE is larger than everything → always valid in right
Median Calculation:
═══════════════════════════════════════════════════════════════
Odd total:
Median = largest in left half
= max(maxLeft1, maxLeft2)
Why? Left half has one more element
That extra element is the median!
Even total:
Median = average of two middle elements
= (max of left + min of right) / 2
= (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2
Time Complexity:
═══════════════════════════════════════════════════════════════
Binary search on smaller array: O(log(min(m, n)))
Each iteration: O(1) operations
Total: O(log(min(m, n))) ✓
Much better than O(m + n)!
Space: O(1) - only variables
Why the "+1" in Partition Formula
Formula: partition2 = (m + n + 1) / 2 - partition1
The "+1" ensures correct behavior for both odd and even:
Odd total (e.g., 7):
(7 + 1) / 2 = 4
Left half gets 4 elements
Right half gets 3 elements
Median is max of left (the 4th element)
Even total (e.g., 8):
(8 + 1) / 2 = 4
Left half gets 4 elements
Right half gets 4 elements
Median is average of max(left) and min(right)
Without "+1":
Even (8): 8 / 2 = 4 ✓ (correct)
Odd (7): 7 / 2 = 3 ✗ (wrong! should be 4)
The "+1" fixes odd case without breaking even!
⚠️ Common Mistakes to Avoid
Mistake 1: Not searching smaller array
// ❌ WRONG - Might search larger array
// No check for which is smaller
// ✓ CORRECT - Ensure nums1 is smaller
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
Mistake 2: Wrong partition formula
// ❌ WRONG - Missing +1
int partition2 = (m + n) / 2 - partition1;
// ✓ CORRECT - With +1
int partition2 = (m + n + 1) / 2 - partition1;
Mistake 3: Not handling edge cases
// ❌ WRONG - Array out of bounds
int maxLeft1 = nums1[partition1 - 1]; // What if partition1 = 0?
// ✓ CORRECT - Check boundaries
int maxLeft1 = (partition1 == 0) ? Integer.MIN_VALUE : nums1[partition1 - 1];
Mistake 4: Wrong loop condition
// ❌ WRONG - Should be <=
while (left < right) {
// ✓ CORRECT - Inclusive
while (left <= right) {
Mistake 5: Wrong median calculation
// ❌ WRONG - Integer division
return (maxLeft + minRight) / 2;
// ✓ CORRECT - Double division
return (maxLeft + minRight) / 2.0;
🎯 Pattern Recognition
Problem Type: Binary Search on Partition Point
Core Pattern: Find Median via Partitioning
When to Apply:
✓ Need O(log n) for sorted arrays
✓ Find median/kth element
✓ Two sorted arrays
✓ Can't afford O(m + n) merge
✓ Partition-based thinking
Recognition Keywords:
- "Median of two sorted arrays"
- "O(log(m+n))" complexity
- Two sorted arrays
- Can't merge (performance)
Similar Problems:
- Kth Smallest Element in Sorted Matrix (LC 378)
- Find K-th Smallest Pair Distance (LC 719)
- Median of Two Sorted Arrays (LC 4) - This one!
Key Pattern Elements:
┌────────────────────────────────────────────┐
│ Binary Search on Partition: │
│ 1. Search smaller array │
│ 2. Calculate partition2 from partition1 │
│ 3. Check partition validity │
│ 4. Adjust based on comparisons │
│ 5. Calculate median from partition │
│ │
│ NOT searching for value! │
│ Searching for POSITION! │
└────────────────────────────────────────────┘
This is the HARDEST binary search pattern!
🧠 Interview Strategy
Step 1: "Two sorted arrays, O(log) → Binary search"
Step 2: "Don't merge, partition!"
Step 3: "Search in smaller array for efficiency"
Step 4: "Check partition validity with maxLeft ≤ minRight"
Step 5: "Calculate median from partition boundaries"
Key Points to Mention:
- Binary search on PARTITION (not value!)
- Search smaller array: O(log(min(m,n)))
- Formula: partition2 = (m+n+1)/2 - partition1
- Valid: maxLeft1 ≤ minRight2 AND maxLeft2 ≤ minRight1
- Edge cases: MIN_VALUE and MAX_VALUE
- Odd: median = max(maxLeft1, maxLeft2)
- Even: median = avg of max(left) and min(right)
- Adjust partition based on comparisons
- Time: O(log(min(m,n))), Space: O(1)
Why This Approach?
"Instead of merging the arrays which takes O(m+n), I use binary
search to find the correct partition point. I search in the
smaller array for efficiency. For each partition position in
the first array, I calculate the corresponding partition in the
second array such that the left half has (m+n+1)/2 elements. I
check if the partition is valid by ensuring all elements in the
left half are less than or equal to all elements in the right
half. Based on the comparison, I adjust the partition position.
Once I find a valid partition, I calculate the median from the
boundary elements."
The Partition Insight:
"The key insight is that we don't need to actually merge. We
just need to partition both arrays such that all elements on
the left are smaller than all elements on the right. The median
is determined by the boundary elements of this partition."
Handling Edge Cases:
"When the partition is at the array boundaries (0 or length), I
use MIN_VALUE and MAX_VALUE as sentinel values. This prevents
array index errors and ensures the partition validity checks
work correctly."
📝 Quick Revision Notes
🎯 Core Concept:
Median of Two Sorted: Don't merge! Find partition. Binary search on smaller array. Formula: partition2 = (m+n+1)/2 - partition1. Valid: maxLeft1 ≤ minRight2 AND maxLeft2 ≤ minRight1. Median: Odd → max(left), Even → avg(max(left), min(right)). Edge: MIN/MAX_VALUE. O(log(min(m,n)))!
⚡ Quick Implementation:
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.length, n = nums2.length;
int left = 0, right = m;
while (left <= right) {
int p1 = (left + right) / 2;
int p2 = (m + n + 1) / 2 - p1;
int maxL1 = (p1 == 0) ? Integer.MIN_VALUE : nums1[p1-1];
int minR1 = (p1 == m) ? Integer.MAX_VALUE : nums1[p1];
int maxL2 = (p2 == 0) ? Integer.MIN_VALUE : nums2[p2-1];
int minR2 = (p2 == n) ? Integer.MAX_VALUE : nums2[p2];
if (maxL1 <= minR2 && maxL2 <= minR1) {
if ((m+n) % 2 == 0) {
return (Math.max(maxL1,maxL2) + Math.min(minR1,minR2)) / 2.0;
} else {
return Math.max(maxL1, maxL2);
}
} else if (maxL1 > minR2) {
right = p1 - 1;
} else {
left = p1 + 1;
}
}
throw new IllegalArgumentException();
}
🔑 Key Insights:
- Pattern: Binary Search on Partition Point
- Search: Smaller array for O(log(min(m,n)))
- Formula:
p2 = (m+n+1)/2 - p1 - Valid: maxLeft ≤ minRight (both ways)
- Edge: MIN_VALUE (no left), MAX_VALUE (no right)
- Odd Total: median = max(maxLeft1, maxLeft2)
- Even Total: median = (max(left) + min(right)) / 2.0
- Adjust: maxL1 > minR2 → search left, else right
- Time: O(log(min(m,n))), Space: O(1)
🎪 Memory Aid:
"Partition not merge! Search smaller, check boundaries!"
Think: "Binary search on POSITION, not VALUE!"
💡 The Key Insight:
Don't merge arrays!
Find the partition!
Left half: p1 from nums1 + p2 from nums2
Right half: rest
Valid when:
All left ≤ all right
Median from boundaries:
Odd: max(left)
Even: avg(max(left), min(right))
⚠️ Critical Details:
1. Search: Smaller array (swap if needed)
2. Formula: p2 = (m+n+1)/2 - p1 (note +1!)
3. Edge: p == 0 → MIN_VALUE, p == len → MAX_VALUE
4. Valid: maxL1 ≤ minR2 AND maxL2 ≤ minR1
5. Adjust: maxL1 > minR2 → right = p1-1
6. Adjust: maxL2 > minR1 → left = p1+1
7. Loop: while (left <= right) (inclusive!)
8. Median: Use 2.0 for double division
🔥 The Partition Visual:
nums1: [1, 3, 8, 9 | 15]
nums2: [7, 11 | 18, 19, 21, 25]
Left: [1,3,8,9,7,11] maxLeft = max(9,11) = 11
Right: [15,18,19,21,25] minRight = min(15,18) = 15
Valid: 11 ≤ 15 ✓
Total = 11 (odd)
Median = maxLeft = 11 ✓
💡 Why "+1" in Formula:
(m + n + 1) / 2
For odd (7): (7+1)/2 = 4 → left has 4
For even (8): (8+1)/2 = 4 → left has 4
Works for both! Without +1, odd fails!
🧪 Edge Cases
Case 1: Empty array
Input: nums1 = [], nums2 = [1]
Output: 1
(Handle m=0 or n=0)
Case 2: One element each
Input: nums1 = [1], nums2 = [2]
Output: 1.5
Case 3: All from one array
Input: nums1 = [1,2], nums2 = [100,101]
Output: 2.5
(Partition at end of nums1)
Case 4: Interleaved
Input: nums1 = [1,3,5], nums2 = [2,4,6]
Output: 3.5
Case 5: Different sizes
Input: nums1 = [1,2], nums2 = [3,4,5,6]
Output: 3.5
All handled correctly! ✓
Related Patterns
- Kth Smallest Element in Sorted Matrix (LC 378)
- Find K Pairs with Smallest Sums (LC 373)
- Merge k Sorted Lists (LC 23)
Happy practicing! 🎯
Note: This is THE hardest binary search problem on LeetCode! Master the partition concept - it's the key to understanding this beautiful solution!