Median of Two Sorted Arrays
Problem Description
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: 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.
Constraints:
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -106 <= nums1[i], nums2[i] <= 106
Solve it on LeetCode
Approaches
1. Brute Force Approach
Intuition:
The simplest approach to find the median of two sorted arrays is to merge them into a single sorted array, then directly find the median. This approach leverages the idea of merging two arrays, similar to the merge process in merge sort.
Steps:
- Initialize an array to hold the merged elements of the two input arrays.
- Use two pointers to iterate over both arrays and append the smaller element from the two into the merged array.
- If one array is exhausted, append the remaining elements of the other array.
- Calculate the median from the merged array:
- If the size of the merged array is odd, the median is the middle element.
- If the size is even, the median is the average of the two middle elements.
Code:
- Time Complexity: O(m + n), where m and n are the lengths of the two arrays. This is because we iterate through both arrays once.
- Space Complexity: O(m + n) due to the creation of the merged array.
2. Optimized Binary Search Approach
Intuition:
A more efficient approach uses binary search. Instead of merging the entire arrays, we use binary search on the shorter array to partition the two arrays into two halves such that all elements on the left side are less than or equal to all elements on the right side. This way, we can determine the median in O(log(min(m, n))) time.
Steps:
- Make sure to always use binary search on the smaller array to minimize the time complexity.
- Use binary search to find the correct partition:
- Divide both arrays into two halves such that the maximum element on the left is less than or equal to the minimum element on the right from both arrays.
- Once the correct partition is found:
- If the combined length of arrays is even, the median is the average of the maximum element of the left part and the minimum element of the right part.
- If it's odd, the median is the maximum element of the left part.
Code:
- Time Complexity: O(log(min(m, n))), where m and n are the lengths of two input arrays. The binary search is applied on the smaller array.
- Space Complexity: O(1), as no additional space is used other than variable storage.