Maximum Gap

Description

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Return 0 if the array contains less than 2 elements.

Example 1:

Input: [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either
             (3,6) or (6,9) has the maximum difference 3.

Example 2:

Input: [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.

Note:

• You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
• Try to solve it in linear time/space.

Solution(javascript)

/** O(nlog(n))
 * @param {number[]} nums
 * @return {number}
 */
// const maximumGap = function (nums = []) {
//   nums.sort((a, b) => a - b)
//   let max = 0
//   for (let i = 1; i < nums.length; i++) {
//     max = Math.max(max, nums[i] - nums[i - 1])
//   }
//   return max
// }

// Radix Sort
const maximumGap = function (nums = []) {
  const maxValue = Math.max(...nums)
  const countingSort = (place) => {
    const count = []
    nums.forEach((num) => {
      const index = Math.floor(num / place) % 10
      count[index] = count[index] || []
      count[index].push(num)
    })
    return count.reduce((acc, v) => {
      if (v !== undefined) {
        acc = acc.concat(v)
      }
      return acc
    }, [])
  }

  let place = 1
  while (Math.floor(maxValue / place) > 0) {
    nums = countingSort(place)
    place *= 10
  }
  let max = 0
  for (let i = 1; i < nums.length; i++) {
    max = Math.max(max, nums[i] - nums[i - 1])
  }
  return max
}