Discussion on Find the Median Challenge

2 days ago+ 0 comments

Sort, then pick the midpoint seemed the easiest. But sort is O(n log n), right? If so, can we use a better sort and get to O(n)? So,if we look at a sorted array and median is midpoint, then we can assume the NthSmallest integer where n is the midpoint is what we are looking for. Then we only have to adjust our sort until then.

Typescript:

function findNthSmallest(arr: number[], n: number): number {
    let left: number = 0;
    let right: number = arr.length - 1;
    
    while (left <= right) {
        const pivotNdx = partition(arr, left, right);
        
        if (pivotNdx === n) {
            return arr[pivotNdx];
        // we know what's left of index is lower than everything else
        } else if (pivotNdx < n) {
            left = pivotNdx + 1;
        // we know what's right of index is larger than everything else
        } else {
            right = pivotNdx - 1;
        }
    }
}

function partition(arr: number[], left: number, right: number): number {
    const pivot = arr[right];
    let i = left - 1;
    
    for (let j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    
    [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
    return i + 1;
}

function findMedian(arr: number[]): number {
    // find mid smallest number, use own copy of arr
    return findNthSmallest([...arr], Math.floor(arr.length / 2));
}

Cookie support is required to access HackerRank