Median of Two Sorted Arrays
HardPrompt
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] <= 106
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves merging the two sorted arrays into a single sorted array. Once the merged array is created, the median can be easily found based on the total number of elements.
Algorithm
-
- Create a new array
mergedof sizem + n.
- Create a new array
-
- Initialize three pointers:
ifornums1,jfornums2, andkformerged, all starting at 0.
- Initialize three pointers:
-
- While
i < mandj < n, comparenums1[i]andnums2[j]. Add the smaller element tomerged[k]and increment the corresponding pointers.
- While
-
- If any elements remain in
nums1, copy them tomerged.
- If any elements remain in
-
- If any elements remain in
nums2, copy them tomerged.
- If any elements remain in
-
- Calculate the total length
total = m + n.
- Calculate the total length
-
- If
totalis odd, returnmerged[total / 2].
- If
-
- If
totalis even, return the average ofmerged[total / 2 - 1]andmerged[total / 2].
- If
Walkthrough
The most straightforward way to solve this problem is to combine the two sorted arrays, nums1 and nums2, into a single, larger sorted array called merged.
We can use a standard merge algorithm, similar to the one used in Merge Sort. We initialize two pointers, one for each input array, and iteratively pick the smaller of the two elements pointed to, adding it to our merged array and advancing the corresponding pointer.
After one of the arrays is fully traversed, we append the remaining elements of the other array to merged.
Once the merged array of size m + n is complete, finding the median is simple:
- If the total length
m + nis odd, the median is the element at the middle index,merged[(m + n) / 2]. - If the total length is even, the median is the average of the two middle elements,
(merged[(m + n) / 2 - 1] + merged[(m + n) / 2]) / 2.0.
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; int[] merged = new int[m + n]; int i = 0, j = 0, k = 0; while (i < m && j < n) { if (nums1[i] < nums2[j]) { merged[k++] = nums1[i++]; } else { merged[k++] = nums2[j++]; } } while (i < m) { merged[k++] = nums1[i++]; } while (j < n) { merged[k++] = nums2[j++]; } int total = m + n; if (total % 2 == 1) { return (double) merged[total / 2]; } else { int mid1 = merged[total / 2 - 1]; int mid2 = merged[total / 2]; return (double) (mid1 + mid2) / 2.0; } }}Complexity
Time
O(m + n)
Space
O(m + n)
Trade-offs
Pros
Conceptually simple and easy to implement.
Leverages the basic merge operation, which is a fundamental algorithm.
Cons
Inefficient in terms of space, as it requires an auxiliary array of size
m + n.Time complexity does not meet the problem's requirement of
O(log(m+n)).
This approach improves upon the first one by avoiding the creation of a merged array. Instead, it simulates the merge process and only keeps track of the elements that would be at the median positions.
Algorithm
-
- Initialize two pointers
iandjto 0 fornums1andnums2respectively.
- Initialize two pointers
-
- Initialize two variables,
median1andmedian2, to store the two potential middle elements.
- Initialize two variables,
-
- Loop from
count = 0up tototal / 2.
- Loop from
-
- Inside the loop, update
median1 = median2.
- Inside the loop, update
-
- Compare
nums1[i]andnums2[j](handling cases where one pointer has reached the end of its array) and assign the smaller value tomedian2, then increment the corresponding pointer.
- Compare
-
- After the loop, if
totalis odd, the median ismedian2.
- After the loop, if
-
- If
totalis even, the median is(median1 + median2) / 2.0.
- If
Walkthrough
We can find the median without explicitly creating the merged array, thus saving space. The goal is to find the middle element(s) of the conceptual merged array.
Let the total length be total = m + n. We need to find the element(s) at the middle index, which is total / 2. We can iterate total / 2 + 1 times, effectively performing the merge process step-by-step.
We use two pointers, i for nums1 and j for nums2. In each step of the iteration, we advance the pointer that points to the smaller element. We only need to keep track of the last two elements encountered during this traversal, let's call them median1 and median2.
After total / 2 + 1 steps, median2 will hold the value that would be at index total / 2 in the merged array, and median1 will hold the value at total / 2 - 1.
- If
totalis odd, the median ismedian2. - If
totalis even, the median is the average ofmedian1andmedian2.
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; int total = m + n; int i = 0, j = 0; int median1 = 0, median2 = 0; for (int count = 0; count <= total / 2; count++) { median1 = median2; if (i < m && j < n) { if (nums1[i] < nums2[j]) { median2 = nums1[i++]; } else { median2 = nums2[j++]; } } else if (i < m) { median2 = nums1[i++]; } else { median2 = nums2[j++]; } } if (total % 2 == 1) { return (double) median2; } else { return (double) (median1 + median2) / 2.0; } }}Complexity
Time
O(m + n)
Space
O(1)
Trade-offs
Pros
Space complexity is constant,
O(1), which is a significant improvement.Still relatively easy to follow the logic.
Cons
Time complexity is still linear,
O(m + n), which fails to meet the problem's requirement.
This is the most efficient approach, meeting the O(log(min(m, n))) time complexity requirement. The idea is to partition both arrays into two halves, a 'left part' and a 'right part', such that all elements in the left parts are less than or equal to all elements in the right parts. The median can then be found from the boundary elements of these partitions.
Algorithm
-
- Ensure
nums1is the smaller array to optimize the binary search range. If not, swap the arrays.
- Ensure
-
- Initialize binary search variables for
nums1:low = 0,high = m.
- Initialize binary search variables for
-
- Loop while
low <= high:
- Loop while
-
- Calculate
partitionX = (low + high) / 2.
- Calculate
-
- Calculate
partitionY = (m + n + 1) / 2 - partitionX.
- Calculate
-
- Determine the four boundary elements:
maxLeftX,minRightX,maxLeftY,minRightY. Handle edge cases where a partition is empty by usingInteger.MIN_VALUEorInteger.MAX_VALUE.
- Determine the four boundary elements:
-
- Check if the partitions are correct:
maxLeftX <= minRightYandmaxLeftY <= minRightX.
- Check if the partitions are correct:
-
- If correct, calculate and return the median based on whether
m + nis even or odd.
- If correct, calculate and return the median based on whether
-
- If
maxLeftX > minRightY, the partition innums1is too large. Adjust the search space:high = partitionX - 1.
- If
-
- If
maxLeftY > minRightX, the partition innums1is too small. Adjust the search space:low = partitionX + 1.
- If
Walkthrough
The problem of finding the median is equivalent to finding the k-th smallest element, where k is (m+n)/2. This hints at a solution faster than linear time, like binary search.
We can perform a binary search on the smaller of the two arrays to find the correct partition point. Let's assume nums1 is smaller. The goal is to find a partition partitionX in nums1 and a corresponding partitionY in nums2.
The partitions must satisfy two conditions:
- The total number of elements in the combined left part is half of the total elements:
partitionX + partitionY = (m + n + 1) / 2. This formula cleverly handles both odd and even total lengths. - Every element in the left part is less than or equal to every element in the right part. This simplifies to checking if
max(leftX) <= min(rightY)andmax(leftY) <= min(rightX), whereleftXandrightXare the left and right partitions ofnums1, and similarly fornums2.
The binary search adjusts partitionX in nums1 (from low = 0 to high = m). For each partitionX, partitionY is calculated. We then check the condition max(leftX) <= min(rightY). If it's not met, we adjust the search range (low or high) until the correct partition is found.
Once the correct partition is found:
- If
m + nis odd, the median ismax(max(leftX), max(leftY)). - If
m + nis even, the median is(max(max(leftX), max(leftY)) + min(min(rightX), min(rightY))) / 2.0.
Edge cases, such as a partition being empty (e.g., partitionX is 0 or m), must be handled carefully, typically by using Integer.MIN_VALUE and Integer.MAX_VALUE.
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { // Ensure nums1 is the smaller array if (nums1.length > nums2.length) { return findMedianSortedArrays(nums2, nums1); } int m = nums1.length; int n = nums2.length; int low = 0; int high = m; while (low <= high) { int partitionX = (low + high) / 2; int partitionY = (m + n + 1) / 2 - partitionX; // Get the four boundary elements int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1]; int minRightX = (partitionX == m) ? Integer.MAX_VALUE : nums1[partitionX]; int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1]; int minRightY = (partitionY == n) ? Integer.MAX_VALUE : nums2[partitionY]; // Check if we found the correct partition if (maxLeftX <= minRightY && maxLeftY <= minRightX) { // Calculate the median if ((m + n) % 2 == 0) { return (double) (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2.0; } else { return (double) Math.max(maxLeftX, maxLeftY); } } else if (maxLeftX > minRightY) { // Move towards the left in nums1 high = partitionX - 1; } else { // Move towards the right in nums1 low = partitionX + 1; } } // Should not happen if inputs are sorted arrays throw new IllegalArgumentException("Input arrays are not sorted."); }}Complexity
Time
O(log(min(m, n)))
Space
O(1)
Trade-offs
Pros
Optimal time complexity of
O(log(min(m, n))).Space efficient with
O(1)space complexity.Directly addresses the problem's constraints and requirements.
Cons
The logic is significantly more complex than the brute-force approaches.
Implementation requires careful handling of multiple edge cases (empty partitions, even/odd total length), making it prone to errors.
Solutions
Solution
public class Solution { private int m; private int n; private int[] nums1; private int[] nums2; public double FindMedianSortedArrays(int[] nums1, int[] nums2) { m = nums1.Length; n = nums2.Length; this.nums1 = nums1; this.nums2 = nums2; int a = f(0, 0, (m + n + 1) / 2); int b = f(0, 0, (m + n + 2) / 2); return (a + b) / 2.0; } private int f(int i, int j, int k) { if (i >= m) { return nums2[j + k - 1]; } if (j >= n) { return nums1[i + k - 1]; } if (k == 1) { return Math.Min(nums1[i], nums2[j]); } int p = k / 2; int x = i + p - 1 < m ? nums1[i + p - 1] : 1 << 30; int y = j + p - 1 < n ? nums2[j + p - 1] : 1 << 30; return x < y ? f(i + p, j, k - p) : f(i, j + p, k - p); }}class Solution {private int m;private int n;private int[] nums1;private int[] nums2;public double findMedianSortedArrays(int[] nums1, int[] nums2) { m = nums1.length; n = nums2.length; this.nums1 = nums1; this.nums2 = nums2; int a = f(0, 0, (m + n + 1) / 2); int b = f(0, 0, (m + n + 2) / 2); return (a + b) / 2.0; }private int f(int i, int j, int k) { if (i >= m) { return nums2[j + k - 1]; } if (j >= n) { return nums1[i + k - 1]; } if (k == 1) { return Math.min(nums1[i], nums2[j]); } int p = k / 2; int x = i + p - 1 < m ? nums1[i + p - 1] : 1 << 30; int y = j + p - 1 < n ? nums2[j + p - 1] : 1 << 30; return x < y ? f(i + p, j, k - p) : f(i, j + p, k - p); }}/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number} */ var findMedianSortedArrays = function (nums1, nums2) { const m = nums1.length; const n = nums2.length; const f = (i, j, k) => { if (i >= m) { return nums2[j + k - 1]; } if (j >= n) { return nums1[i + k - 1]; } if (k == 1) { return Math.min(nums1[i], nums2[j]); } const p = Math.floor(k / 2); const x = i + p - 1 < m ? nums1[i + p - 1] : 1 << 30; const y = j + p - 1 < n ? nums2[j + p - 1] : 1 << 30; return x < y ? f(i + p, j, k - p) : f(i, j + p, k - p); }; const a = f(0, 0, Math.floor((m + n + 1) / 2)); const b = f(0, 0, Math.floor((m + n + 2) / 2)); return (a + b) / 2; };class Solution {public: double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) { int m = nums1.size(), n = nums2.size(); function<int(int, int, int)> f = [&](int i, int j, int k) { if (i >= m) { return nums2[j + k - 1]; } if (j >= n) { return nums1[i + k - 1]; } if (k == 1) { return min(nums1[i], nums2[j]); } int p = k / 2; int x = i + p - 1 < m ? nums1[i + p - 1] : 1 << 30; int y = j + p - 1 < n ? nums2[j + p - 1] : 1 << 30; return x < y ? f(i + p, j, k - p) : f(i, j + p, k - p); }; int a = f(0, 0, (m + n + 1) / 2); int b = f(0, 0, (m + n + 2) / 2); return (a + b) / 2.0; }};class Solution: # Division a // b : floordiv(a, b) midVal1 = nums1 [ i + k // 2 - 1 ] if i + k // 2 - 1 < m else math . inf midVal2 = nums2 [ j + k // 2 - 1 ] if j + k // 2 - 1 < n else math . inf if midVal1 < midVal2 : return findKth ( i + k // 2 , j , k - k // 2 ) # '+' or '-' k//2 else : return findKth ( i , j + k // 2 , k - k // 2 ) m = len ( nums1 ) n = len ( nums2 ) # Division a // b : floordiv(a, b) left = ( m + n + 1 ) // 2 right = ( m + n + 2 ) // 2 return ( findKth ( 0 , 0 , left ) + findKth ( 0 , 0 , right )) / 2.0 ############ # iteration version class Solution ( object ): def findMedianSortedArrays ( self , nums1 , nums2 ): a , b = sorted (( nums1 , nums2 ), key = len ) m , n = len ( a ), len ( b ) after = ( m + n - 1 ) / 2 lo , hi = 0 , m while lo < hi : i = ( lo + hi ) / 2 if after - i - 1 < 0 or a [ i ] >= b [ after - i - 1 ]: hi = i else : lo = i + 1 i = lo nextfew = sorted ( a [ i : i + 2 ] + b [ after - i : after - i + 2 ]) return ( nextfew [ 0 ] + nextfew [ 1 - ( m + n ) % 2 ]) / 2.0 def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: def findKth(i: int, j: int, k: int) -> float: if i >= m: return nums2[j + k - 1] if j >= n: return nums1[i + k - 1] if k == 1: return min(nums1[i], nums2[j])Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.