Median of Two Sorted Arrays
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
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Constraints:
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
In order to solve this problem we need to be clear about what a median is. According to Wikipedia "the median is the value separating the higher half from the lower half of a data sample, a population, or a probability distribution." Since we are using it in the data set case we continue with their definition of "For a data set, it may be thought of as the middle value". So, we are looking for the middle value of the combined inputs. A trivial way to find this answer is to merge the two inputs together and split it at the middle. The problem with this solution is that it has a time complexity of O(nlogn) and the question requires a runtime of O(log (m+n)). However knowing that both inputs are sorted we can use that to basically do a binary search to find the places to split the arrays so that we have all the smallest numbers on one side and all the largest numbers on the other. Let's get started with the problem skeleton.
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
}
Now we need to think about what we need to keep track of. First since the inputs can be of different lengths we need to make sure that we are doing the search for a good split position on the shortest array. We can set up a couple of variables to track the shortest and longest array.
var findMedianSortedArrays = function(nums1, nums2) {
let shortest = nums1.length > nums2.length ? nums2 : nums1
let longest = nums1.length > nums2.length ? nums1 : nums2
}
If we pick some random place to split the shorter of the two arrays we need a way to figure out where to split the longer so that sides will be equal (or that the lower values will have at most 1 more item). We can do this by finding the middle of the array if we merged the two arrays together and subtracting out the place we split the shortest array. Javascript only has a number type and we only want an integer here so we will use the Math.ceil (or add 1) to make sure that if the merged array would be odd our smaller number half has the extra value.
var findMedianSortedArrays = function(nums1, nums2) {
let shortest = nums1.length > nums2.length ? nums2 : nums1
let longest = nums1.length > nums2.length ? nums1 : nums2
let totalMiddle = Math.ceil((shortest.length + longest.length) / 2)
}
Finally keep track of the starting and ending point of what we are splitting on the smaller array. Since we are splitting the entire array the first time we do the split we will initialize them with values that encompass the entire short array.
var findMedianSortedArrays = function(nums1, nums2) {
let shortest = nums1.length > nums2.length ? nums2 : nums1
let longest = nums1.length > nums2.length ? nums1 : nums2
let totalMiddle = Math.ceil((shortest.length + longest.length) / 2)
let start = 0
let end = shortest.length
}
We need to continue splitting the smaller array until we find the point where all the values on the "left side" of our two splits are all less than all the values on the "right sides". We can set up a loop and run it until our start or end overlaps the other value.
var findMedianSortedArrays = function(nums1, nums2) {
let shortest = nums1.length > nums2.length ? nums2 : nums1
let longest = nums1.length > nums2.length ? nums1 : nums2
let totalMiddle = Math.ceil((shortest.length + longest.length) / 2)
let start = 0
let end = shortest.length
while (start <= end) {
}
}
We will now start a binary search on the smaller array trying to find the point in that array where when we split it, it allows us to get the numbers for both arrays split at the points where all of our low values are collected and all our high values are collected. Let's split the shorter array right in the middle and based on that split figure out where we need to split the longer array. Remember we said that we can find thiat by finding the middle of the array if we merged the two arrays together and subtracting out the place we split the shortest array.
var findMedianSortedArrays = function(nums1, nums2) {
let shortest = nums1.length > nums2.length ? nums2 : nums1
let longest = nums1.length > nums2.length ? nums1 : nums2
let totalMiddle = Math.ceil((shortest.length + longest.length) / 2)
let start = 0
let end = shortest.length
while (start <= end) {
let shortestSplit = Math.floor((start + end) /2)
let longestSplit = totalMiddle - shortestSplit
}
}
Okay, we now have places that we can split the input arrays that will give us equal numbers of values if we add the two bottom splits together and compare them to the number of values of the two upper splits. Next we need to make sure that those splits give us all the lower numbers for all the total numbers in the lower splits and all the higher numbers for all the total numbers in the upper split. Since the original input arrays were sorted we know that the highest number in each lower split is less than the lowest number in it's corresponding split so really we just need to check if the highest number in the first inputs split is lower than the lowest number in the second inputs higher split and vice versa for the second inputs lower split and first inputs higher split. Let's see if we can make more sense of that in code. Let's first compare the top value in the shorter input's lower split to the lowest value in the longer input's upper split.
var findMedianSortedArrays = function(nums1, nums2) {
let shortest = nums1.length > nums2.length ? nums2 : nums1
let longest = nums1.length > nums2.length ? nums1 : nums2
let totalMiddle = Math.ceil((shortest.length + longest.length) / 2)
let start = 0
let end = shortest.length
while (start <= end) {
let shortestSplit = Math.floor((start + end) /2)
let longestSplit = totalMiddle - shortestSplit
if (shortestSplit > start && shortest[shortestSplit - 1] > longest[longestSplit]) {
}
}
}
We also made a check to verify that our split is still higher than the beginning index of our current split. If the highest value is greater than the lowers value of the longer inputs lowest value in its upper split we haven't got our splits correctly and we need to slide our split left or lower to remove that higher number.
var findMedianSortedArrays = function(nums1, nums2) {
let shortest = nums1.length > nums2.length ? nums2 : nums1
let longest = nums1.length > nums2.length ? nums1 : nums2
let totalMiddle = Math.ceil((shortest.length + longest.length) / 2)
let start = 0
let end = shortest.length
while (start <= end) {
let shortestSplit = Math.floor((start + end) /2)
let longestSplit = totalMiddle - shortestSplit
if (shortestSplit > start && shortest[shortestSplit - 1] > longest[longestSplit]) {
end = end - 1
}
}
}
We will do the same thing if we find that the larger array's upper lower bound has a number higher than the smaller arrays higher bound. If this is the case we will need to slide the starting point up or to the right.
var findMedianSortedArrays = function(nums1, nums2) {
let shortest = nums1.length > nums2.length ? nums2 : nums1
let longest = nums1.length > nums2.length ? nums1 : nums2
let totalMiddle = Math.ceil((shortest.length + longest.length) / 2)
let start = 0
let end = shortest.length
while (start <= end) {
let shortestSplit = Math.floor((start + end) /2)
let longestSplit = totalMiddle - shortestSplit
if (shortestSplit > start && shortest[shortestSplit - 1] > longest[longestSplit]) {
end = end - 1
} else if (shortestSplit < end && longest[longestSplit - 1] > shortest[shortestSplit]) {
start = start + 1
}
}
}
If neither of these cases are true it means we found the perfect splits to the input arrays that keep all the lower numbers in a lower bounds and all the higher numbers in the higher bounds. If this is the case we just need to get the highest number from the lower bounds groups and the lowest number from the higher bounds groups. Let's work on getting the maximum from the left splits first since if the total merged array would be odd and we stored that extra value on the left splits we know that we can just return that number. If either split was done at index 0 then we know that it's going to be empty, which tells us that we just need to return the last number from the other split. Remember that the shortestSplit and longestSplit variables are just references to an index in the input arrays where the split would happen.
var findMedianSortedArrays = function(nums1, nums2) {
let shortest = nums1.length > nums2.length ? nums2 : nums1
let longest = nums1.length > nums2.length ? nums1 : nums2
let totalMiddle = Math.ceil((shortest.length + longest.length) / 2)
let start = 0
let end = shortest.length
while (start <= end) {
let shortestSplit = Math.floor((start + end) /2)
let longestSplit = totalMiddle - shortestSplit
if (shortestSplit > start && shortest[shortestSplit - 1] > longest[longestSplit]) {
end = end - 1
} else if (shortestSplit < end && longest[longestSplit - 1] > shortest[shortestSplit]) {
start = start + 1
} else {
if (shortestSplit == 0) {
maxLeftSplits = longest[longestSplit - 1]
} else if (longestSplit == 0) {
maxLeftSplits = shortest[shortestSplit - 1]
}
}
}
}
If both of the splits would have values then we just need to take the max of the last value of each split.
var findMedianSortedArrays = function(nums1, nums2) {
let shortest = nums1.length > nums2.length ? nums2 : nums1
let longest = nums1.length > nums2.length ? nums1 : nums2
let totalMiddle = Math.ceil((shortest.length + longest.length) / 2)
let start = 0
let end = shortest.length
while (start <= end) {
let shortestSplit = Math.floor((start + end) /2)
let longestSplit = totalMiddle - shortestSplit
if (shortestSplit > start && shortest[shortestSplit - 1] > longest[longestSplit]) {
end = end - 1
} else if (shortestSplit < end && longest[longestSplit - 1] > shortest[shortestSplit]) {
start = start + 1
} else {
if (shortestSplit == 0) {
maxLeftSplits = longest[longestSplit - 1]
} else if (longestSplit == 0) {
maxLeftSplits = shortest[shortestSplit - 1]
} else {
maxLeftSplits = Math.max(shortest[shortestSplit - 1], longest[longestSplit - 1])
}
}
}
}
Again, if the total merged array would be odd we know that this value would be the median since we stored the extra value on the lower side. We make our check for that and return that value if it's true.
var findMedianSortedArrays = function(nums1, nums2) {
let shortest = nums1.length > nums2.length ? nums2 : nums1
let longest = nums1.length > nums2.length ? nums1 : nums2
let totalMiddle = Math.ceil((shortest.length + longest.length) / 2)
let start = 0
let end = shortest.length
while (start <= end) {
let shortestSplit = Math.floor((start + end) /2)
let longestSplit = totalMiddle - shortestSplit
if (shortestSplit > start && shortest[shortestSplit - 1] > longest[longestSplit]) {
end = end - 1
} else if (shortestSplit < end && longest[longestSplit - 1] > shortest[shortestSplit]) {
start = start + 1
} else {
if (shortestSplit == 0) {
maxLeftSplits = longest[longestSplit - 1]
} else if (longestSplit == 0) {
maxLeftSplits = shortest[shortestSplit - 1]
} else {
maxLeftSplits = Math.max(shortest[shortestSplit - 1], longest[longestSplit - 1])
}
if ((shortest.length + longest.length) % 2 == 1) {
return maxLeftSplits
}
}
}
}
If the merged array would end up having an even number of items in it we need to find the average of the highest low value and the lowest high value. Since we already have the highest low value we just need to find the lowers high value. We will do nearly the same thing as when we found the highest low, we will make sure both splits would have values or return the first item of the one with values or if both splits would have values we return the min of the lowest value in each.
var findMedianSortedArrays = function(nums1, nums2) {
let shortest = nums1.length > nums2.length ? nums2 : nums1
let longest = nums1.length > nums2.length ? nums1 : nums2
let totalMiddle = Math.ceil((shortest.length + longest.length) / 2)
let start = 0
let end = shortest.length
while (start <= end) {
let shortestSplit = Math.floor((start + end) /2)
let longestSplit = totalMiddle - shortestSplit
if (shortestSplit > start && shortest[shortestSplit - 1] > longest[longestSplit]) {
end = end - 1
} else if (shortestSplit < end && longest[longestSplit - 1] > shortest[shortestSplit]) {
start = start + 1
} else {
if (shortestSplit == 0) {
maxLeftSplits = longest[longestSplit - 1]
} else if (longestSplit == 0) {
maxLeftSplits = shortest[shortestSplit - 1]
} else {
maxLeftSplits = Math.max(shortest[shortestSplit - 1], longest[longestSplit - 1])
}
// Here is our return if the merged array would have an odd lenght
if ((shortest.length + longest.length) % 2 == 1) {
return maxLeftSplits
}
let minRightSplits = 0
if (shortestSplit == shortest.length) {
minRightSplits = longest[longestSplit]
} else if (longestSplit == longest.length) {
minRightSplits = shortest[shortestSplit]
} else {
minRightSplits = Math.min(longest[longestSplit], shortest[shortestSplit])
}
}
}
}
All that is left to do now is to return the average of those value.
var findMedianSortedArrays = function(nums1, nums2) {
let shortest = nums1.length > nums2.length ? nums2 : nums1
let longest = nums1.length > nums2.length ? nums1 : nums2
let totalMiddle = Math.ceil((shortest.length + longest.length) / 2)
let start = 0
let end = shortest.length
while (start <= end) {
let shortestSplit = Math.floor((start + end) /2)
let longestSplit = totalMiddle - shortestSplit
if (shortestSplit > start && shortest[shortestSplit - 1] > longest[longestSplit]) {
end = end - 1
} else if (shortestSplit < end && longest[longestSplit - 1] > shortest[shortestSplit]) {
start = start + 1
} else {
if (shortestSplit == 0) {
maxLeftSplits = longest[longestSplit - 1]
} else if (longestSplit == 0) {
maxLeftSplits = shortest[shortestSplit - 1]
} else {
maxLeftSplits = Math.max(shortest[shortestSplit - 1], longest[longestSplit - 1])
}
// Here is our return if the merged array would have an odd lenght
if ((shortest.length + longest.length) % 2 == 1) {
return maxLeftSplits
}
let minRightSplits = 0
if (shortestSplit == shortest.length) {
minRightSplits = longest[longestSplit]
} else if (longestSplit == longest.length) {
minRightSplits = shortest[shortestSplit]
} else {
minRightSplits = Math.min(longest[longestSplit], shortest[shortestSplit])
}
return (maxLeftSplits + minRightSplits) / 2
}
}
}