2
\$\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\$
3
\$\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, privacy policy and cookie policy

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