Blind 75 - problem 14 : Median of Two Sorted Arrays

 Problem Statement:

Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The answer is guaranteed to be unique.

Implement the function:

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2);

Optimal Approach:

The most efficient way to solve this problem is by using Binary Search. The idea is to partition the two arrays into two halves such that:

1. The left half contains half of the elements, and the right half contains the other half.
2. The largest element on the left side is smaller than the smallest element on the right side.

Using binary search on the smaller array, we find the correct partition and compute the median in O(log(min(m, n))) time, which is optimal.

Steps:

1. Ensure that nums1 is the smaller array for easier handling.
2. Use binary search to partition nums1 such that the left half contains the smaller half of the combined arrays.
3. Adjust the partition in nums2 accordingly.
4. Once the partition is found, calculate the median based on the maximum element of the left side and the minimum element of the right side.

LeetCode-Compatible Code Implementation:

#include <vector>
#include <algorithm>
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(), n = nums2.size();
        int left = 0, right = m;
        
        while (left <= right) {
            int partition1 = (left + right) / 2;
            int partition2 = (m + n + 1) / 2 - partition1;
            
            int maxLeft1 = (partition1 == 0) ? INT_MIN : nums1[partition1 - 1];
            int minRight1 = (partition1 == m) ? INT_MAX : nums1[partition1];
            
            int maxLeft2 = (partition2 == 0) ? INT_MIN : nums2[partition2 - 1];
            int minRight2 = (partition2 == n) ? INT_MAX : nums2[partition2];
            
            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                if ((m + n) % 2 == 0) {
                    return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0;
                } else {
                    return max(maxLeft1, maxLeft2);
                }
            } else if (maxLeft1 > minRight2) {
                right = partition1 - 1;
            } else {
                left = partition1 + 1;
            }
        }
        
        throw invalid_argument("Input arrays are not sorted.");
    }
};

Step-by-Step Explanation of Code:

1. Handle the smaller array first:

   • If nums1 is larger than nums2, swap them to reduce the binary search complexity.

2. Initialize binary search:

   • Set up binary search on nums1 to partition the arrays.

3. Calculate partitions:

   • For each partition, calculate the corresponding partition in nums2.
   • Get the elements on the left and right sides of the partitions for both arrays.

4. Check the condition:

   • If the largest element on the left side is smaller than the smallest element on the right side (for both arrays), we’ve found the correct partition.
   • Compute the median based on whether the total number of elements is odd or even.

5. Adjust the partition:

   • If the left partition's elements are too large, move the partition to the left.
   • If the left partition's elements are too small, move the partition to the right.

Dry Run / Execution Steps:

Let’s dry-run the algorithm with the sample input.

Input:

nums1 = [1, 3]
nums2 = [2]

Step-by-Step Execution:

1. Ensure nums1 is the smaller array:

   nums1 = [1, 3], nums2 = [2]
   

2. Apply binary search on nums1:

   • left = 0, right = 2, calculate partition1 = 1, partition2 = 1.

3. Compare the maximum and minimum elements on the left and right sides:

   maxLeft1 = 1, minRight1 = 3
   maxLeft2 = 2, minRight2 = INT_MAX
   

4. Since maxLeft1 <= minRight2 and maxLeft2 <= minRight1, calculate the median:

   Median = (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2 = (max(1, 2) + min(3, INT_MAX)) / 2 = (2 + 3) / 2 = 2.0
   

Output:

Output = 2.0

Alternative Approaches & Why Not?

1. Brute Force: Merge the two arrays and then find the median. This approach would take O(m + n) for merging and O(m + n) for finding the median, which results in O(m + n) time complexity. This is less optimal than binary search.

2. Sorting: Sort the two arrays and find the median. This approach takes O((m + n) log(m + n)) time, which is slower than the binary search approach.

3. Two Pointers: Use two pointers to merge the arrays and then find the median. This also takes O(m + n) time, which is slower than binary search for large inputs.

Best Solution & Why It’s Best:

The binary search solution is the most efficient. It operates in O(log(min(m, n))) time, which is much faster than merging or sorting the arrays. It uses constant space, making it optimal in terms of both time and space.

Approach	Time Complexity	Space Complexity
Brute Force	O(m + n)	O(m + n)
Sorting	O((m + n) log(m + n))	O(m + n)
Binary Search	O(log(min(m, n)))	O(1)

Complexity Analysis:

• Time Complexity:

  • Brute Force: O(m + n)
  • Sorting: O((m + n) log(m + n))
  • Binary Search: O(log(min(m, n)))

• Space Complexity:

  • Brute Force: O(m + n)
  • Sorting: O(m + n)
  • Binary Search: O(1)

Conclusion:

The binary search approach is the most efficient solution for finding the median of two sorted arrays. For practice, you can try similar problems like:

• Kth Largest Element in an Array
• Merge k Sorted Lists