Find Median of Two Sorted Arrays in JS

Question

The task is taken from leetcode

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

My solution

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
 let i1 = i2 = 0;
 let smallest, valBefore;
 const pivot = Math.floor((nums1.length + nums2.length) / 2);
 while (nums1[i1] || nums2[i2]) {
 smallest = (nums2[i2] === void 0 || nums1[i1] < nums2[i2])
 ? nums1[i1++]
 : nums2[i2++];
 if ((nums1.length + nums2.length) % 2) {
 if (pivot === i1 + i2 - 1) {
 return smallest;
 }
 } else {
 if (pivot - 1 === i1 + i2 - 1) {
 valBefore = smallest
 }
 if (pivot === i1 + i2 - 1) {
 return (smallest + valBefore) / 2;
 } 
 }
 }
};

This is the first idea that I had and it reached 99th percentile. I guess you can't take this evaluation seriously. And I'm sure there's a better solution.

• Teepeemm: By the way, you have a bug: if the arrays are both [-1,0,1,2,3,4,5], then nums1[1]||nums2[1] will be false, and the loop will exit.

Answer 1

The 99th percentile is due to the linear nature of your approach. The goal of this exercise is to figure out a logarithmic one.

I don't want to spell out the algorithm entirely. Just a hint to get you started. Take a middle element of nums1. Find its lower bound in nums2; call it i2. In the sorted array the selected element would be at the position nums1.length/2 + i2. I hope the hint is a good enough.

---

pivot doesn't look like a good name to me. totalLength, perhaps?

---

The complicated logic inside the loop also hurts the performance. Consider looping until you reach the midpoint:

 while (i1 + i2 < pivot)

and do the final median finding afterwards.