4 Median of Two Sorted Arrays in Javascript Leetcode Problem

Median of Two Sorted Arrays

Hard

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

Javascript solution to finding median of two sorted arrays:

const findMedian = (arr1, arr2) => {
  const len = arr1.length + arr2.length;
  return len % 2 ? oddMedian(Math.floor(len/2), arr1, arr2) : evenMedian((len/2)-1, len/2, arr1, arr2);
}

const oddMedian = (medianIndex, arr1, arr2) => {
  if (arr1[arr1.length-1] < arr2[0]) {
    if (arr1.length > medianIndex) {
      return arr1[medianIndex];
    } else if (arr1.length <= medianIndex) {
      return arr2[medianIndex - arr1.length];
    }
  } else if (arr2[arr2.length-1] < arr1[0]) {
    if (arr2.length > medianIndex) {
      return arr2[medianIndex];
    } else if (arr2.length <= medianIndex) {
      return arr1[medianIndex - arr2.length];
    }
  } else {
    const [shorterArr, largerArr] = arr1.length < arr2.length ? [arr1, arr2] : [arr2, arr1];
    let j = 0;
    let k = 0;
    const sortedArr = [];
    for (let i = 0; i <= medianIndex; i++) {
      if (shorterArr[j] <= largerArr[k]) {
        sortedArr[i] = shorterArr[j];
        j++;
      } else {
        sortedArr[i] = largerArr[k];
        k++;
      }
    }
    return sortedArr[medianIndex];
  }
}

const evenMedian = (medianIndex1, medianIndex2, arr1, arr2) => {
  if (arr1[arr1.length-1] < arr2[0]) {
    if (arr1.length-1 >= medianIndex2) {
      return (arr1[medianIndex1]+arr1[medianIndex2])/2;
    } else if (arr1.length-1 < medianIndex1) {
      const firstMedianIndex = medianIndex1 - arr1.length;
      return (arr2[firstMedianIndex]+arr2[firstMedianIndex+1])/2;
    } else {
      return (arr1[arr1.length-1] + arr2[0])/2;
    }
  } else if (arr2[arr2.length-1] < arr1[0]) {
    if (arr2.length-1 >= medianIndex2) {
      return (arr2[medianIndex1]+arr2[medianIndex2])/2;
    } else if (arr2.length-1 < medianIndex1) {
      const firstMedianIndex = medianIndex1 - arr2.length;
      return (arr1[firstMedianIndex]+arr1[firstMedianIndex+1])/2;
    } else {
      return (arr2[arr2.length-1] + arr1[0])/2;
    }
  } else {
    const [shorterArr, largerArr] = arr1.length < arr2.length ? [arr1, arr2] : [arr2, arr1];
    let i = 0;
    let j = 0;
    let k = 0;
    const sortedArr = [];
    for (let i = 0; i <= medianIndex2; i++) {
      if (shorterArr[j] <= largerArr[k]) {
        sortedArr.push(shorterArr[j]);
        j++;
      } else {
        sortedArr.push(largerArr[k]);
        k++;
      }
    }
    return (sortedArr[medianIndex1] + sortedArr[medianIndex2])/2;
  }
}

Example

console.log("Result:", findMedian([1,3,5], [2,4,6,8]));
console.log("Result:", findMedian([1,3,5,7,10], [2,4,6,8]));
console.log("Result:", findMedian([1,3,5,7,10], [2,4,6,8,9]));
console.log("Result:", findMedian([1,3,5], [2,4,6,8,9]));
console.log("Result:", findMedian([1,3,5,7], [2,4,6,8,9,10]));
console.log("Result:", findMedian([1,3,5,7,10], [2,4,6]));
console.log("Result:", findMedian([1,3,5,7], [2,4]));
console.log("Result:", findMedian([1,2,4], [3,5,6,7,8,9,10,11]));
console.log("Result:", findMedian([1], [2, 3, 4]));
console.log("Result:", findMedian([1, 2], [3, 4]));
console.log("Result:", findMedian([1], [2, 3]));

Output

Result: 4
Result: 5
Result: 5.5
Result: 4.5
Result: 5.5
Result: 4.5
Result: 3.5
Result: 6
Result: 2.5
Result: 2.5
Result: 2