# Median of 2 sorted arrays, in JS

• Let's try to find the median of 2 sorted arrays, with a log complexity

The median of a sorted array is simply:

``````function median(a) { // warning: works only if a is sorted!
return a.length % 2 ? a[(a.length - 1) / 2] : (a[a.length / 2 - 1] + a[a.length / 2]) / 2;
}
``````

Another interesting thing is that for 2 sorted arrays:

``````median(a) <= median([...a, ...b]) <= median(b)
// or
median(b) <= median([...a, ...b]) <= median(a)
``````

It means we will be able to drop one half of arrays, and recurse

Let's always use `a` the first array as the larger one

``````if (b.length > a.length) {
[a, b] = [b, a];
}
``````

First, some obvious cases, if the 2 arrays are disjoints:

``````if (a[a.length-1] <= b[0]) return median(a.concat(b));
if (b[b.length-1] <= a[0]) return median(b.concat(a));
``````

That's easily improvable in performance, we will show an improved version at the end

Some quick utils for later:

``````var MAX = (x = -Infinity, y = -Infinity) => Math.max(x, y);
var MIN = (x = Infinity, y = Infinity) => Math.min(x, y);
``````

So that we can do safely:

``````const a = [1, 2], i = 1;
console.log(MAX(a[i], a[i+1]/* doesn't exist, so it's undefined*/)) // gives 2
``````

Now, since we are going to iterate, let's deal with stop conditions, that's the hardest part

an easy one:

``````if (b.length === 0) {
return median(a);
}
``````

then 1

``````if (b.length === 1) {
if (a.length % 2) {
if (b[0] < a[(a.length - 1) / 2]) { // we virtually add b[0] in a, just before its median
// so we take the max of b[0] and the previous item in a
return (MAX(a[(a.length - 1) / 2 - 1], b[0]) + a[(a.length - 1) / 2]) / 2;
} else if (b[0] > a[(a.length - 1) / 2]) { // same, but now b[0] does on the right of a's median
return (MIN(a[(a.length - 1) / 2 + 1], b[0]) + a[(a.length - 1) / 2]) / 2;
} else {
return b[0]; // they are equal, so thanks to our interesting property seen at the top, we can finish
}
} else { // similar, but now a changes from an even length to an odd length, when "adding" b[0]
// so the final median is one item
const ma = (a[a.length / 2 - 1] + a[a.length / 2]) / 2;
if (b[0] < ma) {
return MAX(a[a.length / 2 - 1], b[0]);
} else if (b[0] > ma) {
return MIN(a[a.length / 2], b[0]);
} else {
return b[0];
}
}
}
``````

Now the hardest one, 2, initially I didn't do it, but it's needed

``````if (b.length === 2) {
if (a.length % 2) { // this part is still not too complex, we virtually add the 2 b items in a
const ma = a[(a.length - 1) / 2];
if (ma <= b[0]) {
return MIN(a[(a.length - 1) / 2 + 1], b[0]);
} else if (ma >= b[1]) {
return MAX(a[(a.length - 1) / 2 - 1], b[1]);
} else {
return ma;
}
} else { // this one is painful, you end up finding it when trying to pass tests
const ma = (a[a.length / 2 - 1] + a[a.length / 2]) / 2;
if (ma <= b[0]) {
return a[a.length / 2] <= b[0] ?
(a[a.length / 2] + MIN(a[a.length / 2 + 1], b[0])) / 2 :
(b[0] + MIN(a[a.length / 2], b[1])) / 2;
} else if (ma >= b[1]) {
return a[a.length / 2 - 1] >= b[1] ?
(a[a.length / 2 - 1] + MAX(a[a.length / 2 - 2], b[1])) / 2 :
(b[1] + MAX(a[a.length / 2 - 1], b[0])) / 2;
} else {
return (MAX(a[a.length / 2 - 1], b[0]) + MIN(a[a.length / 2], b[1])) / 2;
}
}
}
``````

phew..., good news, now it's almost done

``````// let's calculate median a:
const ma = a.length % 2 ? a[(a.length - 1) / 2] : (a[a.length / 2 - 1] + a[a.length / 2]) / 2;

if (b.length % 2) { // as usual
const mb = b[(b.length - 1) / 2];
if (ma < mb) { // recurse with left part of b and right part of a
// since we remove the same number of items on each side, the median is unchanged
return findMedianSortedArrays(a.slice((b.length-1)/2), b.slice(0, (b.length+1)/2));
} else if (ma > mb) { // recurse with right part of b and left part of a
return findMedianSortedArrays(a.slice(0, a.length - (b.length-1)/2), b.slice((b.length-1)/2));
} else {
return ma; // they are equal, we can stop
}
} else { // similarly
const mb = (b[b.length / 2 - 1] + b[b.length / 2]) / 2;
if (ma < mb) {
// the +1 / -1 below are necessary, we don't split in exact halves, we keep the 2 median items
// you could try slicing with b.length/2 only, and see when it fails
return findMedianSortedArrays(a.slice(b.length/2 - 1), b.slice(0, b.length/2 + 1));
} else if (ma > mb) {
return findMedianSortedArrays(a.slice(0, a.length - b.length/2 + 1), b.slice(b.length/2 - 1));
} else {
return ma;
}
}
``````

Done

Here's the full code:

``````var MAX = (x = -Infinity, y = -Infinity) => Math.max(x, y);
var MIN = (x = Infinity, y = Infinity) => Math.min(x, y);

/**
* @param {number[]} a
* @param {number[]} b
* @return {number}
*/
var findMedianSortedArrays = function(a, b) {
if (b.length > a.length) {
[a, b] = [b, a];
}
// check if disjoints
if (a[a.length-1] <= b[0]) {
const len = a.length + b.length;
return len % 2 ? a[(len - 1) / 2] : (a[len / 2 - 1] + a[len / 2]) / 2;
}
if (b[b.length-1] <= a[0]) {
const len = a.length - b.length;
return len % 2 ? a[(len - 1) / 2] : (a[len / 2 - 1] + a[len / 2]) / 2;
}

if (b.length === 0) {
return a.length % 2 ? a[(a.length - 1) / 2] : (a[a.length / 2 - 1] + a[a.length / 2]) / 2;
}
if (b.length === 1) {
if (a.length % 2) {
if (b[0] < a[(a.length - 1) / 2]) {
return (MAX(a[(a.length - 1) / 2 - 1], b[0]) + a[(a.length - 1) / 2]) / 2;
} else if (b[0] > a[(a.length - 1) / 2]) {
return (MIN(a[(a.length - 1) / 2 + 1], b[0]) + a[(a.length - 1) / 2]) / 2;
} else {
return b[0];
}
} else {
const ma = (a[a.length / 2 - 1] + a[a.length / 2]) / 2;
if (b[0] < ma) {
return MAX(a[a.length / 2 - 1], b[0]);
} else if (b[0] > ma) {
return MIN(a[a.length / 2], b[0]);
} else {
return b[0];
}
}
}

if (b.length === 2) {
if (a.length % 2) {
const ma = a[(a.length - 1) / 2];
if (ma <= b[0]) {
return MIN(a[(a.length - 1) / 2 + 1], b[0]);
} else if (ma >= b[1]) {
return MAX(a[(a.length - 1) / 2 - 1], b[1]);
} else {
return ma;
}
} else {
const ma = (a[a.length / 2 - 1] + a[a.length / 2]) / 2;
if (ma <= b[0]) {
return a[a.length / 2] <= b[0] ?
(a[a.length / 2] + MIN(a[a.length / 2 + 1], b[0])) / 2 :
(b[0] + MIN(a[a.length / 2], b[1])) / 2;
} else if (ma >= b[1]) {
return a[a.length / 2 - 1] >= b[1] ?
(a[a.length / 2 - 1] + MAX(a[a.length / 2 - 2], b[1])) / 2 :
(b[1] + MAX(a[a.length / 2 - 1], b[0])) / 2;
} else {
return (MAX(a[a.length / 2 - 1], b[0]) + MIN(a[a.length / 2], b[1])) / 2;
}
}
}

const ma = a.length % 2 ? a[(a.length - 1) / 2] : (a[a.length / 2 - 1] + a[a.length / 2]) / 2;

if (b.length % 2) {
const mb = b[(b.length - 1) / 2];
if (ma < mb) {
return findMedianSortedArrays(a.slice((b.length-1)/2), b.slice(0, (b.length+1)/2));
} else if (ma > mb) {
return findMedianSortedArrays(a.slice(0, a.length - (b.length-1)/2), b.slice((b.length-1)/2));
} else {
return ma;
}
} else {
const mb = (b[b.length / 2 - 1] + b[b.length / 2]) / 2;
if (ma < mb) {
return findMedianSortedArrays(a.slice(b.length/2 - 1), b.slice(0, b.length/2 + 1));
} else if (ma > mb) {
return findMedianSortedArrays(a.slice(0, a.length - b.length/2 + 1), b.slice(b.length/2 - 1));
} else {
return ma;
}
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.