#4: Median of Two Sorted Arrays

Welcome back to the series! Today we tackle one of the first, but one of the harder LeetCode problems: Median of Two Sorted Arrays.

As always, if you like these posts, be sure to drop a like and star on GitHub! Let's get into the solution.

Game Plan

Let's read the description.

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

Ok, I'm seeing a couple of things here. Some of this information isn't really important because I'm working with JavaScript, so things like length constraints aren't really necessary to take into that much consideration.

The basic plan of attack is to create two functions, one to find the median, and the other to return the sorted median. The second function is the one that's going to be called as the solution to the problem.

Let's tackle the first function first.

Find the Median of an Array

What is a median? It's the middle value of a set of numbers.

[1, 2, 3, 4, 5]        // median would be 3
[1, 2, 3, 4, 5, 6, 7]  // median would be 4

Calling the array something like arr, we can then find the median like this.

let median = arr[Math.floor(arr.length / 2)];

This line will take the middle value of an array. Why does it work?

Consider the first example I gave. That array is 5 elements long, so dividing by 2 will give us 2.5. That's not a valid location in the array, so we have to round up (Math.ceil()) or down (Math.floor()) to the nearest whole number. Because arrays in JS are 0-indexed, we're going to round down to find the true middle value, which in this case would be 2.

We then take that index and plug it into the array to get the median value.

So we have the median, that's fantastic. Unfortunately, there will be cases where the array's length is an even number. That means no true middle value, because there's no middle location. There are the same number of elements on each side of the set!

When it comes to cases like this, we take the two elements closest to the middle and return the average. Here's some examples.

[1, 2, 3, 4, 5, 6]        // median would be (3 + 4) / 2 = 3.5 
[1, 2, 3, 4, 5, 6, 7, 8]  // median would be (4 + 5) / 2 = 4.5

So we need to find the two middle elements and average them. Here's how we would do that.

let median = (arr[arr.length / 2 - 1] + arr[arr.length / 2]) / 2

We had to round when we had an odd number of elements; now, we don't have to because there are an even number. We simply take the half, the half minus 1, and we average them.

So there's the logic for finding the median. The next step is to turn it into a function.

Writing the median function

So let's jump right in and write the function! We need to determine only one thing - whether or not the array is even. I've chosen to codegolf this task, so the following code might look a bit weird. Don't worry - I'll explain.

const findMedian = (arr) => {
    const half = arr.length / 2;
    return arr.length % 2 ? arr[Math.floor(half)] : (arr[half - 1] + arr[half]) / 2;
}

A few things.

1. I've chosen to store the arr.length / 2 value in a variable half because I use it so often. Just a choice, I didn't have to do it this way.
2. I return a ternary operator that evaluates arr.length % 2. If the number is even, this condition will return 0. If not, it'll return some other value. Why? In JavaScript, 0 is evaluated as false, but all other numbers are evaluated as true.
3. Therefore, it follows that if the condition is true we should implement the logic we had for an odd array, and if it is false we should implement the logic we had for an even array.

So there's your function to find the median, given an array. Let's figure out a solution to the main problem using this function.

Putting it all together

We're given two sorted arrays, and we have to merge them into one sorted array. No problem for ES6 syntax!

let sorted = [...nums1, ... nums2].sort((a, b) => a - b);

This line accomplishes two main steps - merging two arrays and sorting the product.

With the spread operator (...), we can combine two arrays easily. Sorting an array is possible with the Array.sort() method, and we sort ascending with (a, b) => a - b. If we wanted descending, we'd do (a, b) => b - a.

Now, the solution is as simple as plugging it into the function we made and returning it to the function they gave us.

const findMedianSortedArrays = (nums1, nums2) => {
    return findMedian([...nums1, ... nums2].sort((a, b) => a - b));
}

With the combination of these two functions, the problem is solved. Happy coding!