Example: Median Of Two Sorted Arrays - rFronteddu/general_wiki GitHub Wiki
Notes:
- Merge sorted array O(n+m) + O(1) to get median
- Include #include to have INT_MAX
- Uses .push_back(a); to append elements
- Even median is (double)(v[n/2 - 1] + v[n/2]) / 2
- Odd mean is (double)(v[n/2])
#include <climits>
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
// brute force
vector<int> merged{};
auto it_1 = nums1.begin();
auto it_2 = nums2.begin();
// merge the two
while(it_1 != nums1.end() || it_2 != nums2.end()) {
int a = it_1 != nums1.end() ? *it_1 : INT_MAX;
int b = it_2 != nums2.end() ? *it_2 : INT_MAX;
if (a < b) {
merged.push_back(a);
++it_1;
} else {
merged.push_back(b);
++it_2;
}
}
// now find median
if(merged.empty()) return 0;
if(merged.size() % 2 == 0) {
return (double) (merged[merged.size()/2 - 1] + merged[merged.size()/2]) / 2;
} else {
return (double)(merged[merged.size()/2]);
}
}
};
We want to partition both arrays into two parts (a Left Half and a Right Half) such that:
- Equal Lengths: Elements in the combined Left Half equal elements in the combined Right Half (or one greater if the total length is odd). The desired len of the left partition is ceiling((n+m)/2)
- Order Property: Every element in the combined Left Half is less than or equal to every component of the combined Right Half.
- If P1 is the len of the left half of nums1, since we want k elements in total in the Left Half, the left half of nums2 must have P2=k-P1 elements
- The Order Property tells us that the perfect partition is found when the following two conditions are simultaneously true:
-
$Max(L_1) \le Min(R_2)$ (The largest element in$nums1$ 's left half is smaller than the smallest element in$nums2$ 's right half). -
$Max(L_2) \le Min(R_1)$ (The largest element in$nums2$ 's left half is smaller than the smallest element in$nums1$ 's right half).
-
- If both are true, we have a valid combined partition, and the median is found!
- If
$Max(L_1) > Min(R_2)$ we move$P_1$ left (high = P_1 - 1) because$MaxL_1$ is too big. We need to move the cut in$nums1$ left to include smaller elements in the Left Half. - If
$Max(L_2) > Min(R_1)$ we Move$P_1$ right (low = P_1 + 1) becayse$MaxL_2$ is too big. We need to move the cut in$nums1$ right to include$MinR_1$ (which is smaller than$MaxL_2$ ) into the Left Half.
#include <climits>
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
// binary search based solution
if(nums1.size() > nums2.size()) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.size();
int n = nums2.size();
// search space for P1
int lo = 0;
int hi = m;
int total_left = (m + n + 1) / 2; // add 1 to ensure at least one el is present
while(lo <= hi) {
// p1 is cut index for nums1, represents number of elements
// in left half of nums 1
int p1 = lo + (hi - lo) / 2;
// p2 is cut index for nums2,
int p2 = total_left - p1;
// max els in left partition of nums1
long long maxL1 = (p1 == 0) ? LLONG_MIN : nums1[p1-1];
// min els in right partition of nums1
long long minR1 = (p1 == m) ? LLONG_MAX : nums1[p1];
// max els in left partition of nums2
long long maxL2 = (p2 == 0) ? LLONG_MIN : nums2[p2-1];
// min els in right partition of nums2
long long minR2 = (p2 == n) ? LLONG_MAX : nums2[p2];
if(maxL1 <= minR2 && maxL2 <= minR1) {
// perfect partition
// odd len
if((m + n) % 2 != 0) {
return (double)std::max(maxL1, maxL2);
} else {
long long left_max = std::max(maxL1, maxL2);
long long right_min = std::min(minR1, minR2);
return (double)(left_max+right_min) / 2.0;
}
} // adjust search
else if (maxL1 > minR2) {
hi = p1 - 1;
} else {
lo = p1 + 1;
}
}
return 0.0; // unreachable in theory
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// first array must be smaller than the second for alg
return nums1.length <= nums2.length ? median(nums1, nums2) : median(nums2, nums1);
}
double median(int[] nums1, int[] nums2) {
// To find the median of two sorted arrays nums1 and nums2,
// we can use the concept of binary search.
// The idea is to partition both arrays such that the elements
// on the left side are smaller than or equal to the elements on the right side.
// Then, the median can be found based on these partitions.
// 1. binary search to find partition point such that
// number of elements on the left of num1 partition l1 +
// number of elements on the left of num2 partition l2 ==
// half of the total number of elements (n + m + 1) / 2
// l1 + l2 = (n + m + 1) / 2
// 2. calculate median based on the partition
int m = nums1.length;
int n = nums2.length;
int left = 0;
int right = m;
while (left <= right) {
int partition1 = left + (right - left) / 2;
// Adding 1 ensures partition2 is at least 1, guaranteeing some elements on the left side of nums2.
int partition2 = (m + n + 1) / 2 - partition1;
// find max element on the left of each partition.
// find min element on the right of each partition.
// Finding elements around partitions
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];
// All elements on the left side of partition1 in nums1 must be less than or equal to
// all elements on the right side of partition2 in nums2
// all elements on the left side of partition2 in nums2 must be less than or equal to
// all elements on the right side of partition1 in nums1.
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
if ((m + n) % 2 == 0) {
return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;
} else {
return Math.max(maxLeft1, maxLeft2);
}
} else if (maxLeft1 > minRight2) {
right = partition1 - 1;
} else {
left = partition1 + 1;
}
}
return -1;
}
}