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).
1#include <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4
5double findMedianSortedArrays(int* nums1, int m, int* nums2, int n) {
6 if (m > n) {
7 return findMedianSortedArrays(nums2, n, nums1, m);
8 }
9 int imin = 0, imax = m, halfLen = (m + n + 1) / 2;
10 while (imin <= imax) {
11 int i = (imin + imax) / 2;
12 int j = halfLen - i;
13 if (i < m && nums2[j - 1] > nums1[i]) {
14 imin = i + 1;
15 } else if (i > 0 && nums1[i - 1] > nums2[j]) {
16 imax = i - 1;
17 } else {
18 int maxLeft = 0;
19 if (i == 0) { maxLeft = nums2[j - 1]; }
20 else if (j == 0) { maxLeft = nums1[i - 1]; }
21 else { maxLeft = (nums1[i - 1] > nums2[j - 1]) ? nums1[i - 1] : nums2[j - 1]; }
22 if ((m + n) % 2 == 1) {
23 return maxLeft;
24 }
25 int minRight = 0;
26 if (i == m) { minRight = nums2[j]; }
27 else if (j == n) { minRight = nums1[i]; }
28 else { minRight = (nums1[i] < nums2[j]) ? nums1[i] : nums2[j]; }
29 return (maxLeft + minRight) / 2.0;
30 }
31 }
32 return 0.0;
33}In this C solution, we first ensure that we perform the binary search on the smaller of the two arrays to maintain efficiency. We set bounds for `i` and adjust those bounds based on comparisons calculated at each step. The correct partitioning of elements between the two arrays determines the median.
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).
1#include
Watch 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 C implementation uses an auxiliary array to merge the two sorted arrays into one. After merging, we calculate the median of the merged array based on its even or odd length. Memory allocation and deallocation are crucial to manage space efficiently.