Find Median of 2 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)).

Naive solution

This would have been very easy if we could do O(n + m) time. We could have just checked the lengths of the arrays, and then used pointers to iterate through both arrays simultaneously until we find the median.

The approach

I attended a lecture where my mentor solved this problem using the same approach I use below in terms of functionality, with a single function. His approach was roughly the following:

If we need O(log(n + m)) time, we have to use binary search. This basically requires this approach:

1. Guess where the median is.
2. Return the answer if your guess was good.
3. Otherwise, based on what your guess turned up, choose where to make your next guess.

That's easy when you have one data structure. But with two, it's more complicated. Where do we guess? How do we know if our answer was right? And if it was wrong, how do we know what direction to go?

Here's a basic set of steps for what my mentor proposed:

1. Guess the middle of the longer array.
2. Check to see if that created an "interleaving window" in the shorter array.
3. Modify the upper and lower bounds based on the direction indicated if we did not find an interleaving window.

An interleaving window is a set of 4 indices:

• 2 adjacent numbers in either array (since it's sorted, they are sorted)
• the smaller number from each array is also smaller than the bigger number in the other array

My goal

I thought it was a fascinating approach, but found it difficult to follow the code. I decided to reimplement the solution using a declarative style, breaking the problem down into its component parts and writing helper functions to perform all the heavy lifting.

Solution

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 * 
 */
var findMedianSortedArrays = function(nums1, nums2) {
    /**
     * Invar: nums1.length >= nums2.length
     * this makes things a lot simpler.
    */
    if (nums2.length > nums1.length) {
        return findMedianSortedArrays(nums2, nums1);
    }

    // Handle some trivial base cases.
    const totalLength = nums1.length + nums2.length;
    if (totalLength === 1) {
        return nums1[0];
    }
    if (totalLength === 2) {
        const number2 = nums1[1] || nums2[0] || 0;
        return (nums1[0] + number2) / 2;
    }

    /**
    * Returns the lower median index of an array of length n.
    * Lower median is the median of an odd-length arrary,
    * or the lower median of an even-length array.
    */
    function getLowerMedian(n) {
        if (n === 0) {
            return -1;
        }
        if (n === 1) {
            return 0;
        }
        return Math.floor((n - 1) / 2);
    }

    // This is a very important number. It will get referred to a lot.
    const totalSteps = getLowerMedian(totalLength);

    // Base case where nums2 is empty
    // Return the median of nums1.
    if (totalLength === nums1.length) {
        if (totalLength % 2 === 0) {
            return (nums1[totalSteps] + nums1[totalSteps + 1]) / 2;
        }
        return (nums1[totalSteps]);
    }

    /**
     * Given an initial guess and the upper and lower bounds,
     * guess and modify the bounds until the answer is found.
     */
    function solve(myGuess, upperBound, lowerBound) {
        const answer = check(myGuess);
        if (typeof answer === "number") {
            return answer;
        }

        if (answer === "Go Left") {
            upperBound = myGuess - 1;
        } else {
            lowerBound = myGuess + 1;
        }
        if (lowerBound === upperBound) {
            return solve(lowerBound, lowerBound, lowerBound);
        }

        const nextGuess = lowerBound + getLowerMedian(upperBound - lowerBound);
        if (nextGuess <= -1) {
            // nums1 is entirely too LARGE
            return (nums1[0] + nums2[nums2.length - 1]) / 2;
        }

        if (nextGuess > (nums1.length - 1)) {
            // nums1 is entirely too SMALL
            return (nums1[nums1.length - 1] + nums2[0]) / 2;
        }

        return solve(nextGuess, upperBound, lowerBound);
    }

    /**
    * Check if an index of nums1 creates an interleaving window.
    * An interleaving window means that we have found the place where nums1 and nums2 intersect.
    * 
    * @param n {number}
    * A guess of the number of steps being taken into nums1.
    * The remaining steps would need to be taken in nums2.
    * 
    * @return {number} or {string}
    * if number, it's the answer!
    * if string, it's the direction you should go in nums1
    */
    function check(n) {
        const nums2Steps = (totalSteps - n);

        // In these cases, we have asked too much or too little of nums2.
        if (nums2Steps < 0) {
            return "Go Left";
        }
        if (nums2Steps > nums2.length) {
            return "Go Right";
        }

        // Create the "window".
        const small1 = nums1[n];
        // Check the type because 0 is falsy but valid.
        // This is easier than checking against the length because we could go over or under.
        const big1 = typeof nums1[n + 1] === "number" ? nums1[n + 1] : Infinity;
        const small2 = typeof nums2[nums2Steps - 1] === "number" ? nums2[nums2Steps - 1] : -Infinity;
        const big2 = typeof nums2[nums2Steps] === "number" ? nums2[nums2Steps] : Infinity;

        // Check the window. If true, we have found the answer.
        if (small1 <= big2 && small2 <= big1) {
            const lowerMedian = Math.max(small1, small2);
            const upperMedian = Math.min(big1, big2);
            if (totalLength % 2 === 0) {
                return (lowerMedian + upperMedian) / 2;
            }
            return lowerMedian;
        }
        if (small1 > big2) {
            return "Go Left";
        }
        return "Go Right";
    }

    // Our initial guess is the middle of nums1
    return solve(getLowerMedian(nums1.length), nums1.length - 1, 0);
};

export default findMedianSortedArrays;

Big O Analysis

Time Complexity: O(log (max(m, n)))

Explanation: The solution uses binary search on the longest array to find the median.