Missing Test Case - 4. Median of Two Sorted Arrays #32563
Description
LeetCode Username
n1Ab9cYSpB
Problem Number, Title, and Link
- Median of Two Sorted Arrays
Bug Category
Problem constraints, Problem hints
Bug Description
Given two sorted arrays nums1 and nums2, find the median of the combined sorted array without explicitly merging them.
The median is the middle element if the total number of elements is odd.
If the total number of elements is even, the median is the average of the two middle elements.
The challenge is to do this efficiently in logarithmic time relative to the combined size
Language Used for Code
C++
Code used for Submit/Run operation
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size())
return findMedianSortedArrays(nums2, nums1);
int m = nums1.size();
int n = nums2.size();
int low = 0, high = m;
while (low <= high) {
int partitionX = (low + high) / 2;
int partitionY = (m + n + 1) / 2 - partitionX;
int maxLeftX = (partitionX == 0) ? INT_MIN : nums1[partitionX - 1];
int minRightX = (partitionX == m) ? INT_MAX : nums1[partitionX];
int maxLeftY = (partitionY == 0) ? INT_MIN : nums2[partitionY - 1];
int minRightY = (partitionY == n) ? INT_MAX : nums2[partitionY];
if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
if ((m + n) % 2 == 0) {
return (double)(max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2;
} else {
return (double)max(maxLeftX, maxLeftY);
}
} else if (maxLeftX > minRightY) {
high = partitionX - 1;
} else {
low = partitionX + 1;
}
}
throw invalid_argument("Input arrays are not sorted or invalid.");
}
};Expected behavior
We perform a binary search on the smaller array to find a partition such that:
Left partition contains half of the combined elements.
All elements in left partitions of both arrays are less than or equal to all elements in right partitions.
Then median is computed based on max of left parts and min of right parts
Screenshots
No response
Additional context
No response