Median of Two Sorted Arrays

Q: What is the best time complexity for Median of Two Sorted Arrays?

Optimal (binary search on the partition) runs in O(log(min(m, n))) time and O(1) extra space. The binary search halves the range of possible cuts in the shorter array each step.

Q: Which pattern does Median of Two Sorted Arrays use?

It is a binary search problem that uses the binary search on partition pattern.

Q: Is there a brute force solution for Median of Two Sorted Arrays?

Yes. Brute force (merge into a new array) takes O(m + n) time and O(m + n) space. Merge the two sorted arrays into one sorted array with the usual two-pointer merge, then read the middle element (odd total) or average the two middle elements (even total).

Q: Which edge cases should I test for Median of Two Sorted Arrays?

One array is empty; Every value of one array is smaller than every value of the other; Total length is odd versus even; Many duplicates, including the same value in both arrays; Both arrays have a single element.

Hard Binary Search Binary Search on Partition Original on LeetCode

Reported atMicrosoft Adobe

Median of Two Sorted Arrays is a hard binary search problem solved with the binary search on partition pattern. The best approach, optimal (binary search on the partition), runs in O(log(min(m, n))) time and O(1) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (merge into a new array) up.

Problem

You are given two arrays nums1 (length m) and nums2 (length n), each sorted in non-decreasing order. Return the median of all m + n values taken together.

The median is the middle value of the combined sorted order when the total count is odd, and the average of the two middle values when it is even. Aim for a solution that runs in O(log(m + n)) time.

Examples

Example 1

Input: nums1 = [2, 9, 14], nums2 = [5, 6]
Output: 6.00000
Why: Together the values are [2, 5, 6, 9, 14]; the middle one of five is 6.

Example 2

Input: nums1 = [1, 8], nums2 = [3, 4, 10, 12]
Output: 6.00000
Why: The merged order is [1, 3, 4, 8, 10, 12]; with six values the median is (4 + 8) / 2 = 6.

Example 3

Input: nums1 = [], nums2 = [-7, -2]
Output: -4.50000
Why: One array can be empty; the median of [-7, -2] is (-7 + -2) / 2 = -4.5.

Constraints

0 <= nums1.length, nums2.length <= 1000
1 <= nums1.length + nums2.length <= 2000
-10^6 <= nums1[i], nums2[i] <= 10^6
Both arrays are sorted in non-decreasing order.
Target: O(log(m + n)) time.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00

Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

Approach	Time	Space
Brute force (merge into a new array)	`O(m + n)`	`O(m + n)`
Better (merge only up to the middle, O(1) space)	`O(m + n)`	`O(1)`
Optimal (binary search on the partition)	`O(log(min(m, n)))`	`O(1)`

1Brute force (merge into a new array)

TimeO(m + n)Every element of both arrays is copied once.

SpaceO(m + n)The merged array holds all m + n values.

Merge the two sorted arrays into one sorted array with the usual two-pointer merge, then read the middle element (odd total) or average the two middle elements (even total).

Create an array of size m + n and fill it by repeatedly taking the smaller front element of the two inputs.
Copy whatever remains of either array.
If the total n is odd, return merged[n / 2]; otherwise return (merged[n / 2 - 1] + merged[n / 2]) / 2.0.

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] merged = new int[m + n];
        int i = 0, j = 0, k = 0;
        while (i < m && j < n) merged[k++] = nums1[i] <= nums2[j] ? nums1[i++] : 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 merged[total / 2];
        return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
    }
}

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m, n = len(nums1), len(nums2)
        merged = []
        i = j = 0
        while i < m and j < n:
            if nums1[i] <= nums2[j]:
                merged.append(nums1[i])
                i += 1
            else:
                merged.append(nums2[j])
                j += 1
        merged.extend(nums1[i:])
        merged.extend(nums2[j:])
        total = m + n
        if total % 2 == 1:
            return float(merged[total // 2])
        return (merged[total // 2 - 1] + merged[total // 2]) / 2.0

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        vector<int> merged(m + n);
        int i = 0, j = 0, k = 0;
        while (i < m && j < n) merged[k++] = nums1[i] <= nums2[j] ? nums1[i++] : 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 merged[total / 2];
        return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
    }
};

function findMedianSortedArrays(nums1, nums2) {
    const m = nums1.length, n = nums2.length;
    const merged = new Array(m + n);
    let i = 0, j = 0, k = 0;
    while (i < m && j < n) merged[k++] = nums1[i] <= nums2[j] ? nums1[i++] : nums2[j++];
    while (i < m) merged[k++] = nums1[i++];
    while (j < n) merged[k++] = nums2[j++];
    const total = m + n;
    if (total % 2 === 1) return merged[Math.floor(total / 2)];
    return (merged[total / 2 - 1] + merged[total / 2]) / 2;
}

2Better (merge only up to the middle, O(1) space)

TimeO(m + n)About half of all elements are stepped over before the middle is reached.

SpaceO(1)Only a few pointers and two remembered values.

Run the same two-pointer merge but do not store anything. Count the elements as they come out in sorted order and remember only the last two. Stop once you reach position (m + n) / 2; the last one, or the average of the last two, is the median.

Keep pointers i and j, plus prev and cur for the last two values taken.
Repeat (m + n) / 2 + 1 times: prev = cur; cur = the smaller of nums1[i] and nums2[j] (taking from whichever array still has elements), advancing that pointer.
If m + n is odd return cur, else return (prev + cur) / 2.0.

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int i = 0, j = 0, prev = 0, cur = 0;
        for (int step = 0; step <= (m + n) / 2; step++) {
            prev = cur;
            if (j >= n || (i < m && nums1[i] <= nums2[j])) cur = nums1[i++];
            else cur = nums2[j++];
        }
        if ((m + n) % 2 == 1) return cur;
        return (prev + cur) / 2.0;
    }
}

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m, n = len(nums1), len(nums2)
        i = j = 0
        prev = cur = 0
        for _ in range((m + n) // 2 + 1):
            prev = cur
            if j >= n or (i < m and nums1[i] <= nums2[j]):
                cur = nums1[i]
                i += 1
            else:
                cur = nums2[j]
                j += 1
        if (m + n) % 2 == 1:
            return float(cur)
        return (prev + cur) / 2.0

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        int i = 0, j = 0, prev = 0, cur = 0;
        for (int step = 0; step <= (m + n) / 2; step++) {
            prev = cur;
            if (j >= n || (i < m && nums1[i] <= nums2[j])) cur = nums1[i++];
            else cur = nums2[j++];
        }
        if ((m + n) % 2 == 1) return cur;
        return (prev + cur) / 2.0;
    }
};

function findMedianSortedArrays(nums1, nums2) {
    const m = nums1.length, n = nums2.length;
    let i = 0, j = 0, prev = 0, cur = 0;
    for (let step = 0; step <= Math.floor((m + n) / 2); step++) {
        prev = cur;
        if (j >= n || (i < m && nums1[i] <= nums2[j])) cur = nums1[i++];
        else cur = nums2[j++];
    }
    if ((m + n) % 2 === 1) return cur;
    return (prev + cur) / 2;
}

3Optimal (binary search on the partition)

TimeO(log(min(m, n)))The binary search halves the range of possible cuts in the shorter array each step.

SpaceO(1)Only indices and four boundary values are stored.

Split the merged order into a left half of half = (m + n + 1) / 2 elements and a right half. If the left half takes i elements from nums1, it must take j = half - i from nums2. The split is right exactly when nums1[i-1] <= nums2[j] and nums2[j-1] <= nums1[i] (treat out-of-range neighbours as minus or plus infinity). If nums1[i-1] is too big, i must shrink; otherwise it must grow, so binary search i over the shorter array. The median then comes from the largest value on the left and the smallest on the right.

Make sure nums1 is the shorter array (swap if needed); let m <= n and half = (m + n + 1) / 2.
Binary search i in [0, m]: j = half - i.
leftA = i > 0 ? nums1[i-1] : -inf, rightA = i < m ? nums1[i] : +inf; leftB and rightB the same way for nums2 and j.
If leftA > rightB, set hi = i - 1; else if leftB > rightA, set lo = i + 1.
Otherwise the split is correct: for odd m + n return max(leftA, leftB); for even return (max(leftA, leftB) + min(rightA, rightB)) / 2.0.

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 half = (m + n + 1) / 2;
        int lo = 0, hi = m;
        while (lo <= hi) {
            int i = (lo + hi) / 2;
            int j = half - i;
            int leftA = i > 0 ? nums1[i - 1] : Integer.MIN_VALUE;
            int rightA = i < m ? nums1[i] : Integer.MAX_VALUE;
            int leftB = j > 0 ? nums2[j - 1] : Integer.MIN_VALUE;
            int rightB = j < n ? nums2[j] : Integer.MAX_VALUE;
            if (leftA > rightB) {
                hi = i - 1;
            } else if (leftB > rightA) {
                lo = i + 1;
            } else {
                int leftMax = Math.max(leftA, leftB);
                if ((m + n) % 2 == 1) return leftMax;
                int rightMin = Math.min(rightA, rightB);
                return (leftMax + (double) rightMin) / 2.0;
            }
        }
        return 0.0;
    }
}

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        m, n = len(nums1), len(nums2)
        half = (m + n + 1) // 2
        lo, hi = 0, m
        while lo <= hi:
            i = (lo + hi) // 2
            j = half - i
            left_a = nums1[i - 1] if i > 0 else -inf
            right_a = nums1[i] if i < m else inf
            left_b = nums2[j - 1] if j > 0 else -inf
            right_b = nums2[j] if j < n else inf
            if left_a > right_b:
                hi = i - 1
            elif left_b > right_a:
                lo = i + 1
            else:
                left_max = max(left_a, left_b)
                if (m + n) % 2 == 1:
                    return float(left_max)
                return (left_max + min(right_a, right_b)) / 2.0
        return 0.0

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) return findMedianSortedArrays(nums2, nums1);
        int m = nums1.size(), n = nums2.size();
        int half = (m + n + 1) / 2;
        int lo = 0, hi = m;
        while (lo <= hi) {
            int i = (lo + hi) / 2;
            int j = half - i;
            int leftA = i > 0 ? nums1[i - 1] : INT_MIN;
            int rightA = i < m ? nums1[i] : INT_MAX;
            int leftB = j > 0 ? nums2[j - 1] : INT_MIN;
            int rightB = j < n ? nums2[j] : INT_MAX;
            if (leftA > rightB) {
                hi = i - 1;
            } else if (leftB > rightA) {
                lo = i + 1;
            } else {
                int leftMax = max(leftA, leftB);
                if ((m + n) % 2 == 1) return leftMax;
                int rightMin = min(rightA, rightB);
                return (leftMax + (double)rightMin) / 2.0;
            }
        }
        return 0.0;
    }
};

function findMedianSortedArrays(nums1, nums2) {
    if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
    const m = nums1.length, n = nums2.length;
    const half = Math.floor((m + n + 1) / 2);
    let lo = 0, hi = m;
    while (lo <= hi) {
        const i = Math.floor((lo + hi) / 2);
        const j = half - i;
        const leftA = i > 0 ? nums1[i - 1] : -Infinity;
        const rightA = i < m ? nums1[i] : Infinity;
        const leftB = j > 0 ? nums2[j - 1] : -Infinity;
        const rightB = j < n ? nums2[j] : Infinity;
        if (leftA > rightB) {
            hi = i - 1;
        } else if (leftB > rightA) {
            lo = i + 1;
        } else {
            const leftMax = Math.max(leftA, leftB);
            if ((m + n) % 2 === 1) return leftMax;
            return (leftMax + Math.min(rightA, rightB)) / 2;
        }
    }
    return 0;
}

Edge cases to test

One array is empty
Every value of one array is smaller than every value of the other
Total length is odd versus even
Many duplicates, including the same value in both arrays
Both arrays have a single element

Hints

Hint 1

The median only depends on the one or two values in the middle of the merged order. Do you need to build the whole merged array?

Hint 2

Cut nums1 after i elements and nums2 after j elements with i + j = (m + n + 1) / 2. The cut is correct when everything on the left is <= everything on the right.

Hint 3

Only two comparisons decide whether a cut is correct: nums1[i-1] <= nums2[j] and nums2[j-1] <= nums1[i]. Binary search i over the shorter array.

FAQ

What is the best time complexity for Median of Two Sorted Arrays?

Optimal (binary search on the partition) runs in O(log(min(m, n))) time and O(1) extra space. The binary search halves the range of possible cuts in the shorter array each step.

Which pattern does Median of Two Sorted Arrays use?

It is a binary search problem that uses the binary search on partition pattern.

Is there a brute force solution for Median of Two Sorted Arrays?

Yes. Brute force (merge into a new array) takes O(m + n) time and O(m + n) space. Merge the two sorted arrays into one sorted array with the usual two-pointer merge, then read the middle element (odd total) or average the two middle elements (even total).

Which edge cases should I test for Median of Two Sorted Arrays?

One array is empty; Every value of one array is smaller than every value of the other; Total length is odd versus even; Many duplicates, including the same value in both arrays; Both arrays have a single element.