In this LeetCode challenge we’re provided with two ordered arrays, and asked to find the median value.
Just to clarify, the median is the middle value. So for example, the median of the array [1,2,3]
would be 2. However, if there are an odd number of values, then the median is the average (mean) of the middle two values. So in an array of [1,2,3,4]
the median value is the average (mean) of 2 and 3, which is 2.5.
Solution #1: The power of JavaScript
Okay, so this is kind of like cheating. With JavaScript, we can concatenate (combine) the arrays, sort them into ascending order, and then just pluck out the middle number(s). This makes things incredibly simple, but isn’t all that efficient:
var findMedianSortedArrays = function (nums1, nums2) { | |
// Merge and sort the arrays | |
const mergedArrays = nums1.concat(nums2); | |
mergedArrays.sort((a, b) => a - b); | |
// Obtain the middle (middle-left if there are an even number of elements) point | |
const middleLeft = Math.floor(mergedArrays.length / 2); | |
// Check if there are an odd number of values | |
if (mergedArrays.length % 2) { | |
// Return the middle value | |
return mergedArrays[middleLeft]; | |
} else { | |
// Return the average of the middle 2 values | |
return (mergedArrays[middleLeft] + mergedArrays[middleLeft + 1]) / 2; | |
} | |
}; |
Solution #2: Looping to the middle
I came up with this idea while trying to crack the “correct” approach (see below). Basically, we start by figuring out the middle point of the combined array, and then we loop towards that point, pulling in the lower value of each array as we do, 1 element at a time, until we reach the middle. Once we reach the middle, we know we’re at the median.
var findMedianSortedArrays = function (nums1, nums2) { | |
// Store the total length of the two arrays combined | |
const totalLength = nums1.length + nums2.length; | |
// Store the middle point (rounding down for even lengths) | |
const halfWayPoint = Math.floor(totalLength / 2); | |
// Counters to track progress through each array | |
let nums1Pos = 0; | |
let nums2Pos = 0; | |
let lastNum, secondToLastNum; | |
// Loop until we reach the half-way point | |
for (let i = 0; i <= halfWayPoint; i++) { | |
// Store the previous number | |
secondToLastNum = lastNum; | |
// If we've run out of numbers in array 2, or if the next number in array 1 comes before (is lower than) the next number in array 2 | |
if ( | |
nums2[nums2Pos] == undefined || | |
(nums1[nums1Pos] != undefined && nums1[nums1Pos] <= nums2[nums2Pos]) | |
) { | |
// Store the next number in array 1 and increment its counter | |
lastNum = nums1[nums1Pos]; | |
nums1Pos++; | |
} else { | |
// Store the next number in array 2 and increment its counter | |
lastNum = nums2[nums2Pos]; | |
nums2Pos++; | |
} | |
} | |
// Return either the last number, or an average of the last 2 numbers, depending on whether the array was odd or even (had 1 or 2 middle number(s)) | |
return totalLength % 2 ? lastNum : (lastNum + secondToLastNum) / 2; | |
}; |
This approach is actually really quite efficient (faster than 97% of JavaScript submissions at the time of writing), but isn’t particularly mathematical, which is what most submissions on LeetCode seem to suggest.
Solution #3: The “right” approach (binary searching)
I’ll be honest and up front here: I do not like this solution at all. Despite being elegant and (eventually) understandable, it’s just not what good programming is to me. If I were to ask someone during an interview to solve this problem (which I would never do), I would be perfectly happy with them spending 5–10 minutes on providing me with either of the above two solutions. Watching them struggle for 45 minutes on this approach would have no value to me.
As a matter of fact, even though I do now, after many hours, finally understand this approach, I just don’t see the point in me writing one out. Instead, this fantastic video will take you through the math behind it and provide some code, in far simpler terms than the “Solution” page on LeetCode.
Top comments (0)