Median of two sorted arrays JavaScript

Question

Trying to find the median of two sorted arrays in O(log(m+n)) or better. I believe this is O(log(m+n) or O(log(m)) or O(n).

var findMedianSortedArrays = function(nums1, nums2) {
 let ar = []
 let len = nums1.length + nums2.length
 let half;
 if (len % 2 === 0) {
 half = len / 2
 } else {
 half = Math.ceil(len / 2)
 }
 for (let i = 0, r1 = 0, r2 = 0; i <= len; i++) {
 if (r1 >= nums1.length || nums1[r1] > nums2[r2]) ar[i] = nums2[r2++]
 else ar[i] = nums1[r1++]
 if (!nums1[i] && nums1.length === r1) {
 ar = ar.concat(nums2.slice(r2))
 return median(ar, len)
 }
 if (!nums2[i] && nums2.length === r2) {
 ar = ar.concat(nums1.slice(r1))
 return median(ar, len)
 }
 if (half === i) {
 return median(ar, len)
 }
 }
 function median(arr, len) {
 if (len % 2 === 0) {
 let half = len / 2
 return median = (arr[half - 1] + arr[half]) / 2
 } else {
 let half = Math.ceil(len / 2)
 return median = arr[half - 1]
 }
 }
}
console.log(findMedianSortedArrays([1, 4], [2, 3, 5, 6]))

• AJNeufeld: You are using concat(), so your implementation is at \$O(m)\,ドル or perhaps \$O(n)\$.
• Rick: @AJNeufeld good point, I did not realize concat runs in O(n). Any suggestions would be appreciated

Answer 1

Unnecessary storage

The current implementation basically processes the two input arrays in parallel, taking the next smaller element from the appropriate array, and appending to ar, until either the end of an input array is reached, or the counter i reaches half.

• If the end of an input array was reached, the remaining elements of the other array are appended to ar. The size of ar becomes len.

• If the counter i reaches half, then nothing is appended to ar. At this point the size of ar is half.

Then, the median function doesn't actually pick the median of the array parameter, but it computes a value based on the len parameter.

The ar array is unnecessary storage. In the end, only the half-th and possibly the half + 1-th values will be used.

The benefit of the ar storage is it makes it simple to compute the median in the case when the end of an input array was reached. In this case, without ar, it's not trivial to find the correct index.

An alternative algorithm is possible without extra storage: - pick values from the input arrays - if we haven't reached yet either end, take the next smaller element - otherwise, if we reached the end of the first array, take the next element from the second - otherwise, if we reached the end of the second array, take the next element from the first - before the above conditions, save the previously picked value in a variable

After counting until half elements, you can compute the value of the median based on len, prev and current.

Like this:

 for (let i = 0, r1 = 0, r2 = 0; i <= half; i++) {
 prev = current;
 if (r1 < nums1.length && r2 < nums2.length) {
 if (nums1[r1] < nums2[r2]) {
 current = nums1[r1++];
 } else {
 current = nums2[r2++];
 }
 } else if (r1 < nums1.length) {
 current = nums1[r1++];
 } else if (r2 < nums2.length) {
 current = nums2[r2++];
 }
 }
 if (prev === undefined) {
 return current;
 }
 if (len % 2 === 0) {
 return (prev + current) / 2;
 }
 return current;

Unnecessary computation

The median helper function recomputes half. You could simply reuse the half variable that's already computed in the closure.

The loop condition i <= len is unnecessary. It will always be true, because the implementation in the loop body guarantees that i will never reach len.

Return value in case of empty input arrays

In case of empty input arrays, the implementation returns NaN. I'm not sure that's correct, or expected. Unless the exercise specifies to return NaN in this case, I think returning undefined makes more sense.