Median Of Two Sorted Arrays Solution for Amazon
Company: Amazon · Difficulty: Hard · Topics: Array, Binary Search, Divide and Conquer
Problem Statement
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)).
Examples
Example 1:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Example 3:
Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000
Explanation: merged array = [0,0,0,0] and median is 0.
Example 4:
Input: nums1 = [], nums2 = [1]
Output: 1.00000
Explanation: merged array = [1] and median is 1.
Intuition
The key insight is to use binary search to find the correct partition of both arrays such that all elements on the left side are smaller than all elements on the right side. This allows us to find the median without actually merging the arrays.
Approach
Approach 1: Binary Search (Optimal)
1. Ensure nums1 is the smaller array
2. Use binary search on the smaller array to find the correct partition
3. Calculate the corresponding partition in the larger array
4. Check if the partition is correct (all left elements ≤ all right elements)
5. Return the median based on the partition
Approach 2: Merge and Find
1. Merge the two sorted arrays
2. Find the median of the merged array
3. Less efficient but straightforward
Approach 3: Two Pointers
1. Use two pointers to traverse both arrays
2. Count elements until reaching the median position
3. Inefficient for large arrays
Dry Run
Let's trace through Example 1: nums1 = [1,3], nums2 = [2]
Binary Search Approach:
- nums1 = [1,3], nums2 = [2]
- Total elements = 3 (odd), median position = 1
- Binary search on nums1 to find partition
- Partition nums1: left = [1], right = [3]
- Partition nums2: left = [2], right = []
- Check: max(left) = 2, min(right) = 3
- Since 2 ≤ 3, partition is correct
- Median = max(left) = 2
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution 1: Binary Search (Optimal)
Time Complexity: O(log(min(m,n))) - Binary search on smaller array
Space Complexity: O(1) - Constant extra space
Solution 2: Merge and Find
Time Complexity: O(m+n) - Merge arrays
Space Complexity: O(m+n) - Merged array
Solution 3: Two Pointers
Time Complexity: O(m+n) - Traverse both arrays
Space Complexity: O(1) - Constant extra space