4. Median of Two Sorted Arrays

📝 Problem Details

• Title: 4. Median of Two Sorted Arrays
• Link: https://leetcode.com/problems/median-of-two-sorted-arrays/
• Difficulty: Hard
• Tags/Categories: Binary-Search

💭What Were My Initial Thoughts?

- naive / brute force would be a merge-and-find approach which is linear in time O(n+m) (this is not efficient enough for the constraints of the question)
- a logarithmic time complexity suggests a binary search approach
- what is the trick to find the median without merging with the help of binary search
- the mid point of our first calculation in a single array finds the "median"
	- how can we apply this rule to our separate subarrays

Key Idea:

• suppose we merge nums1 and nums2 into a single sorted array of length x = n+m
• the median is the element at index x/2 (or the average of the two middle elements if x is even)
• instead of merging, we only need to retrieve the first x/2 elements from both arrays combined
• we can achieve this by using binary search on the smaller array to determine how many elements should come from each array

💡 Explanation of Solution

1. Partitioning Condition
	- we need to divide nums1 and nums2 such that:
		- the left half contains x/2 smallest elements
		- the right half contains the remaining elements
	- we determine a partition index i in nums1, which means taking i elements from nums1
	- the remaining x/2-i elements must come from nums2

2. Finding the Correct Partition
	- we adjust i (the partition index in nums1) using binary search to satisfy:
		- nums1[i - 1] ≤ nums2[j] (ensuring the left half is correctly partitioned)
		- nums2[j - 1] ≤ nums1[i] (ensuring the right half is correctly partitioned)
	- if nums1[i - 1] > nums2[j] , it means we took too many elements from nums1, so we move left
	- if nums2[j - i] > nums1[i] , it means we took too few elements from nums1, so we move right

3. Extracting the Median
	- if x is odd: the largest element is in the left half
		- max(nums1[i - 1], nums2[j - 1])
	- if x is even: the largest element is the average of the largest element in the left half and the smallest element in the right half
		- (max(nums1[i - 1], nums2[j - 1]) + min(nums1[i], nums2[j])) / 2

⌛ Complexity Analysis

Time Complexity: O(log N)

Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // ensure nums1 is the smaller array
        if(nums1.size() > nums2.size()) return findMedianSortedArrays(nums2, nums1);
 
        int n = nums1.size();
        int m = nums2.size();
        int left = 0;
        int right = n;
        int half = (n + m + 1) / 2; // the smallest x/2 elements
 
        while(left <= right) {
            
            int i = left + (right - left) / 2; // partition index in nums1
            int j = half - i; // partition index in nums 2
 
            // boundary conditions
            int leftMax1 = (i == 0) ? INT_MIN : nums1[i - 1];
            int rightMin1 = (i == n) ? INT_MAX : nums1[i];
            int leftMax2 = (j == 0) ? INT_MIN : nums2[j - 1];
            int rightMin2 = (j == m) ? INT_MAX : nums2[j];
 
            // valid partition found
            if(leftMax1 <= rightMin2 && leftMax2 <= rightMin1) {
                if((n+m) % 2 == 0) {
                    return (max(leftMax1, leftMax2) + min(rightMin1, rightMin2)) / 2.0;
                } else {
                    return max(leftMax1, leftMax2);
                }
            }
 
            // adjust binary search range
            else if (leftMax1 > rightMin2) {
                right = i - 1; // move left
            } else {
                left = i + 1; // move right
            }
        }
        return -1;
    }
};