DEV Community

Duncan McArdle
Duncan McArdle

Posted on

1

LeetCode problem #4 — Median of two sorted arrays (JavaScript)

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.

https://www.youtube.com/watch?v=LPFhl65R7ww

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more