medianOfTwoSortedArrays

Hard · Array Manipulations · 2 test cases

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)).

Examples

medianOfTwoSortedArrays([1, 3], [2]) → 2.0
medianOfTwoSortedArrays([1, 2], [3, 4]) → 2.5

Starter code

function medianOfTwoSortedArrays(nums1, nums2) {

}

Complexity of the optimal solution

Time O((n+m) log(n+m)), space O(n+m). This solution merges the two arrays and then sorts the result. Merging takes O(n+m) space. Sorting the merged array of size (n+m) takes O((n+m) log(n+m)) time. (Note: A more optimal O(log(min(n,m))) solution exists but is much more complex).

Solve medianOfTwoSortedArrays in the browser