--- title: Median of Two Sorted Arrays description: Find the median of two sorted arrays with O(log (m+n)) time complexity. date: 2024-03-14 tag: ["Hard", "Array", "Binary Search"] author: Easy Algo premium: false percentage: 30 --- ## Problem > LeetCode link: [Median of Two Sorted Arrays](https://leetcode.com/problems/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 overall run time complexity should be O(log (m+n)). **Example 1:** ``` Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: The merged array = [1,2,3], with median 2. ``` **Example 2:** ``` Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: The merged array = [1,2,3,4], with median (2 + 3) / 2 = 2.5 ``` **Constraints:** ``` nums1.length == m nums2.length == n 0 <= m <= 1000 0 <= n <= 1000 1 <= m + n <= 2000 -10^6 <= nums1[i], nums2[i] <= 10^6 ``` ## Solution **Problem Simplified:** Imagine you have two lines of students sorted by height. You need to find the "middle" height if these lines were merged while maintaining the height order. For an odd total number of students, the middle height is the center student's height. For an even total, it's the average height of the two center students. The challenge is to find this median without actually merging the lines. **Edge Cases and Test Examples:** * **Edge Cases:** * Either `nums1` or `nums2` is empty * Both arrays empty (though problem states m + n ≥ 1) * All elements in one array are smaller/larger than all elements in the other * **Test Cases:** * `nums1 = [1, 3], nums2 = [2]` → Output: `2.0` * `nums1 = [1, 2], nums2 = [3, 4]` → Output: `2.5` * `nums1 = [], nums2 = [1, 2, 3]` → Output: `2.0` * `nums1 = [1, 2], nums2 = []` → Output: `1.5` * `nums1 = [1, 5], nums2 = [2, 3, 4]` → Output: `3.0` * `nums1 = [1, 2], nums2 = [1, 2, 3]` → Output: `2.0` **Solution Analysis:** | Approach | Advantages | Disadvantages | Time Complexity | Space Complexity | |----------|------------|---------------|----------------|------------------| | Merge and Sort | Simple to understand | Inefficient, doesn't meet requirements | O((m+n)log(m+n)) | O(m+n) | | Two Pointers | No extra space needed | Linear time, doesn't meet requirements | O(m+n) | O(1) | | Binary Search | Optimal time complexity | More complex to understand | O(log(min(m,n))) | O(1) | * **Complexity Analysis:** * Time Complexity: Measures how algorithm runtime scales with input size * Space Complexity: Measures extra space needed as input size grows * O(log n) typically indicates a divide-and-conquer approach **Recommended Approach:** Binary Search **Python Implementation:** **Version 1: With Detailed Comments** ```python def findMedianSortedArrays(nums1, nums2): """ Find the median of two sorted arrays. Args: nums1: First sorted array nums2: Second sorted array Returns: Median of the two arrays """ # Ensure nums1 is the shorter array for efficient binary search if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1 m, n = len(nums1), len(nums2) low, high = 0, m while low <= high: # i is partition in nums1, j is partition in nums2 # Sum of elements on left side equals (m + n + 1) / 2 i = (low + high) // 2 j = (m + n + 1) // 2 - i # Handle edge cases at partitions max_left_nums1 = float('-inf') if i == 0 else nums1[i - 1] min_right_nums1 = float('inf') if i == m else nums1[i] max_left_nums2 = float('-inf') if j == 0 else nums2[j - 1] min_right_nums2 = float('inf') if j == n else nums2[j] # Check if we found the correct partition if max_left_nums1 <= min_right_nums2 and max_left_nums2 <= min_right_nums1: # For even total length, median is average of max left and min right if (m + n) % 2 == 0: return (max(max_left_nums1, max_left_nums2) + min(min_right_nums1, min_right_nums2)) / 2 # For odd total length, median is max of left side else: return max(max_left_nums1, max_left_nums2) # Adjust binary search range based on comparison elif max_left_nums1 > min_right_nums2: high = i - 1 # Move partition left in nums1 else: low = i + 1 # Move partition right in nums1 ``` **Version 2: Clean Implementation** ```python def findMedianSortedArrays(nums1, nums2): if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1 m, n = len(nums1), len(nums2) low, high = 0, m while low <= high: i = (low + high) // 2 j = (m + n + 1) // 2 - i max_left_nums1 = float('-inf') if i == 0 else nums1[i - 1] min_right_nums1 = float('inf') if i == m else nums1[i] max_left_nums2 = float('-inf') if j == 0 else nums2[j - 1] min_right_nums2 = float('inf') if j == n else nums2[j] if max_left_nums1 <= min_right_nums2 and max_left_nums2 <= min_right_nums1: if (m + n) % 2 == 0: return (max(max_left_nums1, max_left_nums2) + min(min_right_nums1, min_right_nums2)) / 2 else: return max(max_left_nums1, max_left_nums2) elif max_left_nums1 > min_right_nums2: high = i - 1 else: low = i + 1 ``` **Step-by-Step Execution:** 1. **Initialization:** * Ensure `nums1` is shorter than `nums2` for efficient binary search * Set up binary search boundaries and array lengths 2. **Binary Search Process:** * Calculate partition points `i` and `j` * Handle edge cases with infinity values * Check if current partition is valid: * If valid, calculate and return median * If not, adjust binary search range 3. **Median Calculation:** * For even total length: average of max left and min right * For odd total length: maximum of left partition 4. **Termination:** * Binary search continues until correct partition is found * Always terminates due to problem constraints