# Median of Two Sorted Arrays **Difficulty:** HARD [External](https://leetcode.com/problems/median-of-two-sorted-arrays) Canonical: https://scaleengineer.com/dsa/problems/median-of-two-sorted-arrays **Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer) **Data structures:** Array **Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Akamai](https://scaleengineer.com/companies/akamai), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Capgemini](https://scaleengineer.com/companies/capgemini), [Cognizant](https://scaleengineer.com/companies/cognizant), [Dropbox](https://scaleengineer.com/companies/dropbox), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [Intuit](https://scaleengineer.com/companies/intuit), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Oracle](https://scaleengineer.com/companies/oracle), [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks), [PayPal](https://scaleengineer.com/companies/paypal), [Pwc](https://scaleengineer.com/companies/pwc), [ServiceNow](https://scaleengineer.com/companies/servicenow), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [VMware](https://scaleengineer.com/companies/vmware), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wipro](https://scaleengineer.com/companies/wipro), [Wix](https://scaleengineer.com/companies/wix), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [PornHub](https://scaleengineer.com/companies/pornhub), [Autodesk](https://scaleengineer.com/companies/autodesk), [Citadel](https://scaleengineer.com/companies/citadel), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Rippling](https://scaleengineer.com/companies/rippling), [Snap](https://scaleengineer.com/companies/snap), [Swiggy](https://scaleengineer.com/companies/swiggy), [Zenefits](https://scaleengineer.com/companies/zenefits) --- ## Problem 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` # Approaches ## Brute Force: Merge and Find Median 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. **Time:** O(m + n) · **Space:** O(m + n) **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))`. ### Explanation 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 + n` is 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`. ```java 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; } } } ``` ### Algorithm - 1. Create a new array `merged` of size `m + n`. - 2. Initialize three pointers: `i` for `nums1`, `j` for `nums2`, and `k` for `merged`, all starting at 0. - 3. While `i < m` and `j < n`, compare `nums1[i]` and `nums2[j]`. Add the smaller element to `merged[k]` and increment the corresponding pointers. - 4. If any elements remain in `nums1`, copy them to `merged`. - 5. If any elements remain in `nums2`, copy them to `merged`. - 6. Calculate the total length `total = m + n`. - 7. If `total` is odd, return `merged[total / 2]`. - 8. If `total` is even, return the average of `merged[total / 2 - 1]` and `merged[total / 2]`. ## Space-Optimized Brute Force 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. **Time:** O(m + n) · **Space:** O(1) **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. ### Explanation 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 `total` is odd, the median is `median2`. * If `total` is even, the median is the average of `median1` and `median2`. ```java 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; } } } ``` ### Algorithm - 1. Initialize two pointers `i` and `j` to 0 for `nums1` and `nums2` respectively. - 2. Initialize two variables, `median1` and `median2`, to store the two potential middle elements. - 3. Loop from `count = 0` up to `total / 2`. - 4. Inside the loop, update `median1 = median2`. - 5. Compare `nums1[i]` and `nums2[j]` (handling cases where one pointer has reached the end of its array) and assign the smaller value to `median2`, then increment the corresponding pointer. - 6. After the loop, if `total` is odd, the median is `median2`. - 7. If `total` is even, the median is `(median1 + median2) / 2.0`. ## Optimal Approach: Binary Search on Partitions 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. **Time:** O(log(min(m, n))) · **Space:** O(1) **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. ### Explanation 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: 1. 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. 2. 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)` and `max(leftY) <= min(rightX)`, where `leftX` and `rightX` are the left and right partitions of `nums1`, and similarly for `nums2`. 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 + n` is odd, the median is `max(max(leftX), max(leftY))`. * If `m + n` is 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`. ```java 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."); } } ``` ### Algorithm - 1. Ensure `nums1` is the smaller array to optimize the binary search range. If not, swap the arrays. - 2. Initialize binary search variables for `nums1`: `low = 0`, `high = m`. - 3. Loop while `low <= high`: - 4. Calculate `partitionX = (low + high) / 2`. - 5. Calculate `partitionY = (m + n + 1) / 2 - partitionX`. - 6. Determine the four boundary elements: `maxLeftX`, `minRightX`, `maxLeftY`, `minRightY`. Handle edge cases where a partition is empty by using `Integer.MIN_VALUE` or `Integer.MAX_VALUE`. - 7. Check if the partitions are correct: `maxLeftX <= minRightY` and `maxLeftY <= minRightX`. - 8. If correct, calculate and return the median based on whether `m + n` is even or odd. - 9. If `maxLeftX > minRightY`, the partition in `nums1` is too large. Adjust the search space: `high = partitionX - 1`. - 10. If `maxLeftY > minRightX`, the partition in `nums1` is too small. Adjust the search space: `low = partitionX + 1`. # Solutions ### CSharp ```csharp 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); } } ``` ### Java ```java 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); } } ``` ### JavaScript ```javascript /** * @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; }; ``` ### CPP ```cpp class Solution { public: double findMedianSortedArrays(vector &nums1, vector &nums2) { int m = nums1.size(), n = nums2.size(); function 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; } }; ``` ### Python ```python 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]) ```