Problem Statement
Given two sorted arrays nums1 and nums2, return the median of the two sorted arrays.
The overall run time complexity should be:
O(log(min(N,M)))
Brute Force Intuition
In an interview, you can explain it like this:
Since both arrays are sorted, we can merge them into a single sorted array and then directly compute the median from the merged array.
Complexity
- Time Complexity: O(N + M)
- Space Complexity: O(N + M)
Brute Force Code
int[] merged = new int[n + m];
// Merge both arrays
return median;
Moving Towards the Optimal Approach
Do we really need the merged array?
No.
We only care about:
Left Half
Right Half
such that:
All elements in Left Half
<=
All elements in Right Half
This is where partition-based Binary Search comes in.
Pattern Recognition
Whenever you see:
- Two Sorted Arrays
- Median
- O(log N) expected
Think:
Binary Search on Partition
Key Observation
For total elements:
n + m
Left partition should contain:
(n + m + 1) / 2
elements.
We Binary Search on:
How many elements to take from nums1
Remaining automatically come from nums2.
Optimal Java Solution
class Solution {
public double findMedianSortedArrays(int[] nums1,
int[] nums2) {
if (nums1.length > nums2.length)
return findMedianSortedArrays(nums2, nums1);
int n1 = nums1.length;
int n2 = nums2.length;
int low = 0;
int high = n1;
while (low <= high) {
int cut1 = low + (high - low) / 2;
int cut2 =
(n1 + n2 + 1) / 2 - cut1;
int left1 =
cut1 == 0 ? Integer.MIN_VALUE
: nums1[cut1 - 1];
int left2 =
cut2 == 0 ? Integer.MIN_VALUE
: nums2[cut2 - 1];
int right1 =
cut1 == n1 ? Integer.MAX_VALUE
: nums1[cut1];
int right2 =
cut2 == n2 ? Integer.MAX_VALUE
: nums2[cut2];
if (left1 <= right2 &&
left2 <= right1) {
if ((n1 + n2) % 2 == 0) {
return (Math.max(left1, left2)
+ Math.min(right1, right2))
/ 2.0;
}
return Math.max(left1, left2);
}
else if (left1 > right2) {
high = cut1 - 1;
} else {
low = cut1 + 1;
}
}
return 0;
}
}
Dry Run
Input
nums1 = [1,3]
nums2 = [2]
Total:
3 elements
Need:
2 elements on left side
Partition:
[1] | [3]
[2] |
Check:
left1 <= right2
left2 <= right1
Valid Partition.
Median:
max(1,2)
=
2
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(log(min(N,M))) |
| Space Complexity | O(1) |
Interview One-Liner
Binary search the partition of the smaller array and ensure all elements on the left side are less than or equal to all elements on the right side.
Pattern Learned
Two Sorted Arrays
+
Median
+
Logarithmic Requirement
=> Binary Search on Partition