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