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 == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106The key challenge in #4 Median of Two Sorted Arrays is finding the median of two sorted arrays without fully merging them. A straightforward idea is to merge both arrays and compute the median, but this leads to O(m + n) time, which does not meet the optimal constraint.
A more efficient method uses binary search with partitioning. The idea is to partition the two arrays such that the combined left half contains exactly half of the elements and every element on the left is less than or equal to those on the right. By performing binary search on the smaller array, we can adjust the partition until this condition is satisfied. Once the correct partition is found, the median can be computed from the boundary elements.
This approach leverages the sorted property of the arrays and achieves O(log(min(m, n))) time complexity with O(1) extra space, making it the most optimal solution commonly expected in coding interviews.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Merge Both Arrays | O(m + n) | O(m + n) |
| Binary Search Partition | O(log(min(m, n))) | O(1) |
Tushar Roy - Coding Made Simple
This approach leverages binary search to reduce the problem to a smaller size, achieving the desired O(log(m + n)) complexity. The strategy involves performing binary search on the smaller array to find the perfect partition point.
Time complexity: O(log(min(m,n))). Space complexity: O(1).
1var findMedianSortedArrays = function(nums1, nums2) {
2 if (nums1.length > nums2.length) {
3 [nums1, nums2] = [nums2, nums1];
4 }
5 let x = nums1.length;
6 let y = nums2.length;
7 let low = 0, high = x;
8 while (low <= high) {
9 let partitionX = (low + high) >> 1;
10 let partitionY = (x + y + 1) >> 1 - partitionX;
11 let maxX = (partitionX === 0) ? -Infinity : nums1[partitionX - 1];
12 let minX = (partitionX === x) ? Infinity : nums1[partitionX];
13 let maxY = (partitionY === 0) ? -Infinity : nums2[partitionY - 1];
14 let minY = (partitionY === y) ? Infinity : nums2[partitionY];
15 if (maxX <= minY && maxY <= minX) {
16 if ((x + y) % 2 === 0) {
17 return ((Math.max(maxX, maxY) + Math.min(minX, minY)) / 2);
18 } else {
19 return Math.max(maxX, maxY);
20 }
21 } else if (maxX > minY) {
22 high = partitionX - 1;
23 } else {
24 low = partitionX + 1;
25 }
26 }
27 throw new Error('Input arrays are not sorted.');
28};JavaScript's `findMedianSortedArrays` similarly navigates the problem utilizing closures and loop constructs that obey the binary search strategy effectively. -Infinity and Infinity act as edge handlers for different partition conditions.
This approach focuses on merging the two sorted arrays as naturally done in merge sort, and then finding the median directly from the merged result. Though this solution has a higher time complexity, it's easier to implement and understand.
Time complexity: O(m + n). Space complexity: O(m + n).
1defWatch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Binary searching the smaller array ensures the algorithm runs in O(log(min(m, n))) time. It also simplifies boundary handling and prevents invalid partitions when adjusting the split between the two arrays.
Yes, this is a well-known hard-level interview problem frequently discussed in FAANG-style interviews. It tests understanding of binary search, edge cases, and how to optimize beyond straightforward merging.
The problem primarily relies on arrays and binary search rather than additional data structures. Since both arrays are already sorted, the algorithm exploits their order to efficiently find the correct partition without merging them.
The optimal approach uses binary search with a partitioning strategy. By partitioning the two arrays so that the left halves contain exactly half the elements, the median can be computed from boundary values. This achieves O(log(min(m, n))) time complexity.
The straightforward Python approach appends both arrays together and sorts them. It finds the median by selecting the middle element(s), depending on the total array length's parity.