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\$ Commented 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\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.