Median of 2 sorted arrays, in JS


  • 0

    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;
    		}
    	}
    };
    

Log in to reply
 

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