LeetCode 4 - Median of Two Sorted Arrays

Problem Statement (LeetCode 4)

Given two sorted arrays nums1 and nums2 of size m and n, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m + n)).

Example Input & Output

Example 1

Input: nums1 = [1,3], nums2 = [2]  
Output: 2.00000  
Explanation: The merged array is [1,2,3] and the median is 2.  

Example 2

Input: nums1 = [1,2], nums2 = [3,4]  
Output: 2.50000  
Explanation: The merged array is [1,2,3,4] and the median is (2+3)/2 = 2.5.  

---

Optimal Approach: Binary Search on the Smaller Array

To solve this problem optimally, we use Binary Search on the smaller array.

Intuition Behind the Approach

Instead of merging both arrays (which takes O(m + n) time), we find the median without merging.

• Partition both arrays at the correct position using Binary Search.
• Ensure equal elements on both sides of the median split.
• Use binary search to adjust the partition until we get correct left and right halves.

Steps to Solve

1. Ensure nums1 is smaller than nums2 to minimize binary search complexity.
2. Perform binary search on nums1 to find partition i, such that:
   • Left partition: contains i elements from nums1 and j = (m + n + 1) / 2 - i elements from nums2.
   • Right partition: contains remaining elements.
3. Check if maxLeft1 <= minRight2 and maxLeft2 <= minRight1.
   • If true, median is found.
   • Else, adjust i using binary search.

---

LeetCode-Compatible C++ Code

#include <vector>
#include <limits.h>
using namespace std;

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) {
            return findMedianSortedArrays(nums2, nums1); // Ensure nums1 is smaller
        }

        int m = nums1.size();
        int n = nums2.size();
        int left = 0, right = m, medianPos = (m + n + 1) / 2;

        while (left <= right) {
            int i = (left + right) / 2;
            int j = medianPos - i;

            int maxLeft1 = (i == 0) ? INT_MIN : nums1[i - 1];
            int minRight1 = (i == m) ? INT_MAX : nums1[i];

            int maxLeft2 = (j == 0) ? INT_MIN : nums2[j - 1];
            int minRight2 = (j == n) ? INT_MAX : nums2[j];

            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                // Found the correct partition
                if ((m + n) % 2 == 0) {
                    return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0;
                } else {
                    return max(maxLeft1, maxLeft2);
                }
            } else if (maxLeft1 > minRight2) {
                right = i - 1; // Move towards left
            } else {
                left = i + 1; // Move towards right
            }
        }

        return 0.0; // Should never reach here
    }
};

---

Step-by-Step Explanation

Binary Search on Smaller Array (nums1)

1. Ensure nums1 is smaller than nums2 to minimize binary search complexity.
2. Binary Search on nums1:
   • Find partition index i in nums1, so j = (m + n + 1) / 2 - i in nums2.
   • maxLeft1 = nums1[i-1], minRight1 = nums1[i].
   • maxLeft2 = nums2[j-1], minRight2 = nums2[j].
3. Check partition conditions:
   • If maxLeft1 <= minRight2 and maxLeft2 <= minRight1, we found the median.
   • If maxLeft1 > minRight2, move right to i-1.
   • Otherwise, move left to i+1.

---

Dry Run with Example

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

Step	Left (l)	Right (r)	Partition i	Partition j	MaxLeft1	MinRight1	MaxLeft2	MinRight2	Condition
1	0	2	1	1	1	3	2	∞	✅ Found Median

• Median = 2.0

---

Alternative Approaches & Why Not?

1. Brute Force (Merging Two Arrays)

• Merge both arrays and find the median.
• Time Complexity: O(m + n)
• Space Complexity: O(m + n)
• ❌ Not optimal due to unnecessary merging.

2. Binary Search on Combined Array

• Store merged elements in a virtual array.
• Time Complexity: O(log(m + n))
• Space Complexity: O(1)
• ✅ Still optimal but slightly harder to implement.

3. Using Heaps (MinHeap & MaxHeap)

• Maintain two heaps: maxHeap for left half, minHeap for right half.
• Time Complexity: O(log(m + n))
• Space Complexity: O(m + n)
• ❌ Extra space required.

---

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Notes
Binary Search on Smaller Array (Best)	O(log(min(m, n)))	O(1)	Most efficient
Merge & Sort	O(m + n)	O(m + n)	Too slow
Heaps (MinHeap & MaxHeap)	O(log(m + n))	O(m + n)	Uses extra space
Binary Search on Combined Array	O(log(m + n))	O(1)	Harder to implement

---

Conclusion

• The binary search approach is the most efficient with O(log(min(m, n))) time complexity and O(1) space complexity.
• Brute force solutions are inefficient and should be avoided.
• Heap-based methods are suboptimal due to extra space usage.

Recommended Problems for Practice

1. Find Kth Smallest Element in a Sorted Matrix
2. Kth Largest Element in an Array
3. Median of a Data Stream

Mastering binary search on partitions is crucial for solving advanced problems efficiently! 🚀