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.

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.