Skip to content

Instantly share code, notes, and snippets.

@fhinkel

fhinkel/maxGap.js

Last active January 11, 2019 17:17
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save fhinkel/690f18c8dfcafd2fc51576e4af97e55e to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save fhinkel/690f18c8dfcafd2fc51576e4af97e55e to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. fhinkel revised this gist Jan 11, 2019. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion maxGap.js
    View file
    Original file line number Diff line number Diff line change
    @@ -10,7 +10,7 @@ const maxGap = (arr) => {
    let range = max - min;
    let lowerBound = range / (n - 1);

    let buckets = []; // n-1 buckets => linear space complexity
    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]) {
  2. fhinkel created this gist Jan 11, 2019.
    43 changes: 43 additions & 0 deletions maxGap.js
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,43 @@
    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 => 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;
    }