3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – Teepeemm
    Feb 13, 2022 at 17:22

1 Answer 1

4
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.