Back to DSA

Median of Two Sorted Arrays

hard
Acceptance: 37%
ArraysTwo Pointers

Two individually sorted arrays of possibly different lengths are provided. Determine the median of the combined collection of elements. The algorithm must run in O(log(m+n)) time, where m and n are the sizes of the two arrays.

Examples

Example 1:
Input:a = [1,4,6], b = [2,3,5]
Output:3.5
Explanation: The merged sequence is [1,2,3,4,5,6]. The median is the average of positions 3 and 4: (3+4)/2 = 3.5.
Example 2:
Input:a = [1,2], b = [3]
Output:2.0
Explanation: Merged: [1,2,3]. The middle element is 2.

Hints

Related Problems

Remove Duplicates from Sorted ArrayeasyBest Time to Buy and Sell StockeasyTwo SumeasyValid PalindromeeasyMerge Sorted Arrayeasy
00:00
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
        int m = nums1.length, n = nums2.length;
        int lo = 0, hi = m;
        while (lo <= hi) {
            int i = (lo + hi) / 2;
            int j = (m + n + 1) / 2 - i;
            int maxLeft1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
            int minRight1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
            int maxLeft2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
            int minRight2 = (j == n) ? Integer.MAX_VALUE : nums2[j];
            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                if ((m + n) % 2 == 0) {
                    return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;
                }
                return Math.max(maxLeft1, maxLeft2);
            } else if (maxLeft1 > minRight2) {
                hi = i - 1;
            } else {
                lo = i + 1;
            }
        }
        return 0.0;
    }
}
Time complexityO(log(min(m, n)))
Space complexityO(1)