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).
1public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
2 if (nums1.Length > nums2.Length) {
3 return FindMedianSortedArrays(nums2, nums1);
4 }
5 int x = nums1.Length;
6 int y = nums2.Length;
7 int low = 0, high = x;
8 while (low <= high) {
9 int partitionX = (low + high) / 2;
10 int partitionY = (x + y + 1) / 2 - partitionX;
11 int maxX = (partitionX == 0) ? int.MinValue : nums1[partitionX - 1];
12 int minX = (partitionX == x) ? int.MaxValue : nums1[partitionX];
13 int maxY = (partitionY == 0) ? int.MinValue : nums2[partitionY - 1];
14 int minY = (partitionY == y) ? int.MaxValue : nums2[partitionY];
15 if (maxX <= minY && maxY <= minX) {
16 if ((x + y) % 2 == 0) {
17 return ((double)Math.Max(maxX, maxY) + Math.Min(minX, minY)) / 2;
18 } else {
19 return (double)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 ArgumentException("Input arrays are not sorted.");
28}C# follows closely with C++ and Java with well-defined partitions and similar boundary handling with int.MinValue and int.MaxValue. The process ensures efficient convergence to the correct median calculation.
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).
1using System;
public class Solution {
public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
int[] mergedArray = new int[nums1.Length + nums2.Length];
int i = 0, j = 0, k = 0;
while (i < nums1.Length && j < nums2.Length) {
if (nums1[i] < nums2[j]) {
mergedArray[k++] = nums1[i++];
} else {
mergedArray[k++] = nums2[j++];
}
}
while (i < nums1.Length) {
mergedArray[k++] = nums1[i++];
}
while (j < nums2.Length) {
mergedArray[k++] = nums2[j++];
}
int totalLength = mergedArray.Length;
if (totalLength % 2 == 0) {
return (mergedArray[totalLength / 2 - 1] + mergedArray[totalLength / 2]) / 2.0;
} else {
return mergedArray[totalLength / 2];
}
}
}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# solution ensures both arrays are merged into a single sorted array, betting on simple logic rather than clever computation. The process easily lets us check the middle element or average them for the median.