Leetcode #164: Maximum Gap

In order to achieve linear time and spacing requirements, we use bucket sort.

func maximumGap(_ nums: [Int]) -> Int {
    if nums.count < 2 {
        return 0
    }
    var minimum = nums[0]
    var maximum = nums[0]
    for i in stride(from: 1, to: nums.count, by: 1) {
        minimum = min(minimum, nums[i])
        maximum = max(maximum, nums[i])
    }
    let length = max(1,Int((maximum-minimum)/(nums.count-1)))
    let bucketCount = Int((maximum-minimum)/length + 1)
    var buckets = Array(repeating: (Int.max,Int.min), count: bucketCount)
    for num in nums {
        let index = Int((num - minimum)/length)
        buckets[index].0 = min(buckets[index].0, num)
        buckets[index].1 = max(buckets[index].1, num)
    }
    var maximumGap = 0
    buckets = buckets.filter { $0.0 != Int.max }
    for i in stride(from: 1, to: buckets.count, by: 1) {
        maximumGap = max(maximumGap, buckets[i].0-buckets[i-1].1)
    }
    return maximumGap
}