maxGap.js

const maxGap = (arr) => {
    const n = arr.length;
    let min = Number.POSITIVE_INFINITY;
    let max = Number.NEGATIVE_INFINITY;
    for (let i = 0; i < n; i++) {
        min = Math.min(arr[i], min);
        max = Math.max(arr[i], max);
    }

    let range = max - min;
    let lowerBound = range / (n - 1);

    let buckets = []; // n-1 buckets, 2 elements each => linear space complexity
    for (let i = 0; i < n; i++) {
        let index = Math.floor((arr[i] - min) / lowerBound);
        if (!buckets[index]) {
            buckets[index] = {};
            buckets[index].left = arr[i];
            buckets[index].right = arr[i];
        } else {
            if (buckets[index].left > arr[i]) {
                buckets[index].left = arr[i]
            }
            if (buckets[index].right < arr[i]) {
                buckets[index].right = arr[i]
            }
        }
    }

    let maxDiff = 0;
    let prev = min;
    for (let i = 0; i < buckets.length; i++) {
        if (!buckets[i]) {
            continue;
        }
        if (buckets[i].left - prev > maxDiff) {
            maxDiff = buckets[i].left - prev;
        }
        prev = buckets[i].right;
    }

    return maxDiff;
}