4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5


/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    // remove elements from both ends

    
    while ((nums1.length + nums2.length)/2 > 1){
        // If any of the arrays is empty, rm the other one
        if(nums1.length == 0){
            nums2.shift();
            nums2.pop();
        } else if(nums2.length == 0){
            nums1.shift();
            nums1.pop();
        } else {
            if(nums1[0] < nums2[0]){
                nums1.shift();
            } else {
                nums2.shift();
            }
            // if nums1 is empty 
            //   OR nums1's tail is less than nums2's, remove nums2
            if(nums1.length == 0 || 
               nums1[nums1.length -1] < nums2[nums2.length -1]){
                nums2.pop();
            } else {
                nums1.pop();
            }
        }
    }
    // only 1 or 2 elements remain now
    var r = nums1.concat(nums2);
    // send average for two
    if(r.length > 1){
        return (r[0]+r[1])/2;
    } else {
    // or just the last element
        return r[0];
    }
};

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.