4. Median of Two Sorted Arrays

Problem

Tags: Array, Binary Search, Divide and Conquer

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

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -10^6 <= nums1[i], nums2[i] <= 10^6

Code

GO

// 4. Median of Two Sorted Arrays (12/7/53377)
// Runtime: 16 ms (63.15%) Memory: 5.38 MB (56.26%) 

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	m, n := len(nums1), len(nums2)
	p1, p2 := 0, 0
	if (m + n) % 2 == 1 {
		for i := 0; i < (m+n)/2; i++ {
			if p1 >= m {
				p2++
			} else if p2 >= n {
				p1++
			} else if nums1[p1] > nums2[p2] {
				p2++
			} else {
				p1++
			}
		}

		if p1 >= m {
            return float64(nums2[p2])
		} else if p2 >= n {
            return float64(nums1[p1])
		} else if nums1[p1] > nums2[p2] {
            return float64(nums2[p2])
		} else {
            return float64(nums1[p1])
		}
	} else {
		for i := 0; i < (m+n)/2-1; i++ {
			if p1 >= m {
				p2++
			} else if p2 >= n {
				p1++
			} else if nums1[p1] > nums2[p2] {
				p2++
			} else {
				p1++
			}
		}

		sum := 0
		for i := 0; i < 2; i++ {
			if p1 >= m {
				sum += nums2[p2]
                p2++
			} else if p2 >= n {
				sum += nums1[p1]
                p1++
			} else if nums1[p1] > nums2[p2] {
				sum += nums2[p2]
                p2++
			} else {
				sum += nums1[p1]
                p1++
			}
		}
        return float64(sum) / 2
	}
}

JS

// 4. Median of Two Sorted Arrays (2/13/53376)
// Runtime: 128 ms (64.51%) Memory: 43.58 MB (94.69%) 

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    const m = nums1.length, n = nums2.length;
    let p1 = 0, p2 = 0;
    if((m + n) % 2) {
        for(var i = 0; i < parseInt((m + n) / 2); i++) {
            if(nums1[p1] === undefined) p2++;
            else if(nums2[p2] === undefined) p1++;
            else if(nums1[p1] > nums2[p2]) p2++;
            else p1++;
        }
        
        if(nums1[p1] === undefined) return nums2[p2];
        if(nums2[p2] === undefined) return nums1[p1];
        return nums1[p1] > nums2[p2] ? nums2[p2] : nums1[p1];
    } else {
        for(var i = 0; i < (m + n) / 2 - 1; i++) {
            if(nums1[p1] === undefined) p2++;
            else if(nums2[p2] === undefined) p1++;
            else if(nums1[p1] > nums2[p2]) p2++;
            else p1++;
        }
        
        let sum = 0;
        for(var i = 0; i < 2; i++) {
            if(nums1[p1] === undefined) sum += nums2[p2++];
            else if(nums2[p2] === undefined) sum += nums1[p1++];
            else if(nums1[p1] > nums2[p2]) sum += nums2[p2++];
            else sum += nums1[p1++];
        }
        return sum / 2;
    }
    
    return 0;
};