Maximum Gap LeetCode solution in JavaScript

1
/**
2
 * The buckets solution.
3
 *
4
 * Time Complexity: O(n)
5
 * Space Complexity: O(n)
6
 *
7
 * @param {number[]} nums
8
 * @return {number}
9
 */
10
var maximumGap = function (nums) {
11
  const n = nums.length;
12

13
  if (n < 2) {
14
    return 0;
15
  }
16

17
  if (n < 3) {
18
    return Math.abs(nums[0] - nums[1]);
19
  }
20

21
  let maxNum = -Infinity;
22
  let minNum = +Infinity;
23

24
  for (let i = 0; i < n; i++) {
25
    maxNum = Math.max(maxNum, nums[i]);
26
    minNum = Math.min(minNum, nums[i]);
27
  }
28

29
  if (maxNum === minNum) {
30
    return 0;
31
  }
32

33
  const k = n - 1;
34
  const averageGap = (maxNum - minNum) / k;
35

36
  const minBuckets = new Array(k);
37
  const maxBuckets = new Array(k);
38

39
  minBuckets[0] = minNum;
40
  maxBuckets[0] = minNum;
41

42
  minBuckets[k - 1] = maxNum;
43
  maxBuckets[k - 1] = maxNum;
44

45
  for (let i = 0; i < n; i++) {
46
    if (minNum === nums[i] || nums[i] === maxNum) {
47
      continue;
48
    }
49

50
    const j = Math.floor((nums[i] - minNum) / averageGap);
51

52
    minBuckets[j] = minBuckets[j] ? Math.min(minBuckets[j], nums[i]) : nums[i];
53
    maxBuckets[j] = maxBuckets[j] ? Math.max(maxBuckets[j], nums[i]) : nums[i];
54
  }
55

56
  let largestGap = 0;
57
  let prevMaxIndex = 0;
58

59
  for (let i = 1; i < n - 1; i++) {
60
    if (minBuckets[i]) {
61
      largestGap = Math.max(
62
        largestGap,
63
        minBuckets[i] - maxBuckets[prevMaxIndex]
64
      );
65
    }
66

67
    if (maxBuckets[i]) {
68
      prevMaxIndex = i;
69
    }
70
  }
71

72
  return largestGap;
73
};