1. Problem Statement (Simple Explanation)
You are given two sorted arrays:
nums1 of size m
nums2 of size n
You need to return the median of the combined data if both arrays were merged into one sorted array.
Constraints:
Total length m + n >= 1
Arrays are individually sorted in non-decreasing order.
You must achieve overall time complexity:
O(log(m+n))
The median:
If total length is odd: middle element.
If total length is even: average of the two middle elements.
2. Examples
Example 1
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: Merged array: [1, 2, 3] and Median = 2
Example 2
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: Merged array: [1, 2, 3, 4] and Median =2+32=2.5
3. Approach 1 – Merge and Find Median (Basic, O(m+n))
Intuition
Simulate the merging step of merge sort:
Merge nums1 and nums2 into a single sorted array (or at least until we reach the median position).
Compute the median from the merged data.
This is simple but runs in:
O(m+n)
which does not meet the required O(log(m+n)) constraint, but is a good starting explanation for beginners.
Algorithm (Step-by-Step)
Let m = len(nums1), n = len(nums2), total = m + n.
Use two pointers i = 0 (for nums1), j = 0 (for nums2).
Option A (fully merge):
Create a new array merged, and push the smaller of nums1[i] and nums2[j] each step.
After merging, if total is odd, return merged[total // 2]; else average merged[total // 2 - 1] and merged[total // 2].
Option B (partial merge, more space efficient):
We only need elements up to the middle indices.
Maintain two variables, prev and curr, updated each step until we reach the median position.
Pseudo-code (Partial Merge)
Complexity
Time: O(m+n)
Space: O(1) extra (with partial merge)
Good for understanding, but not optimal per problem requirement.
4. Approach 2 – Binary Search on Partition (Optimal, O(log(min(m, n))))
This is the standard interview solution.
Key Idea (Partition-Based)
We conceptually partition the combined sorted array into left and right halves such that:
All elements on the left side are <= all elements on the right side.
The left and right halves differ in size by at most 1.
We don’t actually merge, we just find such a partition by using binary search on one array.
We choose nums1 to be the shorter array (swap if needed).
We perform binary search on nums1's partition index i, and derive j for nums2.
Let:
m = len(nums1), n = len(nums2) and assume m <= n.
total = m + n.
half = (total + 1) // 2 → number of elements that should be on the left side combined.
We choose some i from 0 to m, and then:
j=half-i
So:
Left side = nums1[0..i-1] and nums2[0..j-1]
Right side = nums1[i..m-1] and nums2[j..n-1]
We want the partition to be valid:
All elements on left ≤ all elements on right:
nums1[i-1] <= nums2[j] (if i > 0 and j < n)
nums2[j-1] <= nums1[i] (if j > 0 and i < m)
Once we have a valid partition:
If total is odd: median is max(left parts)
If total is even: median is average of max(left parts) and min(right parts)
We adjust i using binary search:
If nums1[i-1] > nums2[j] → i is too big → move left.
Else if nums2[j-1] > nums1[i] → i is too small → move right.
Else → perfect partition.
To avoid index problems at borders, we treat out-of-bounds as ±∞, e.g.:
If i == 0, then left1 = -∞ (no element)
If i == m, then right1 = +∞
Similarly for j.
Pseudo-code (Binary Search on Shorter Array)
Complexity
We binary-search only on the shorter array:
Time: O(log(min(m,n)))
Space: O(1)
Meets the required O(log(m+n)).
5. Java code
6. C code
7. C++ code
8. Python code
9. JavaScript
Comments
Post a Comment