SeaCode

Appearance

Maximum Consecutive Gap ​

Problem 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.

  • You may assume that all the elements in the array are non-negative integers and fit in the 32-bit signed integer range.
  • You may also assume that the difference will not overflow.

Try to solve it in linear time/space

Problem Constraints

1 <= |A| <= 10^6
1 <= Ai <= 10^9

Input Format

The first argument is an integer array A.

Output Format

Return an integer representing maximum difference between the successive elements in array A.

Example Input

A = [1, 10, 5]

Example Output

5

Example Explanation

The maximum difference is between 5 and 10, which is 5.

Solution ​

swift
import Foundation

class Solution {
	func maximumGap(_ A: [Int]) -> Int {
        if A.count < 2 {
            return 0
        }
        
        guard let min = A.min(), let max = A.max() else {
            return 0
        }
       
        if min == max {
            return 0
        }
        
        var gap = (max - min) / (A.count-1)
        if (max - min) % (A.count-1) != 0 {
            gap += 1
        }        
        var buckets = [[Int]](repeating:[Int](),count:A.count)
        for v in A {
            let i = (v - min)/gap
            buckets[i].append(v)  
        }        
        var maxGap = 0
        var pre = min
        for b in buckets {
            
            if b.count == 0 {
                continue
            }
            
            let min = b.min() ?? 0
            if (min - pre) > maxGap {
                maxGap = (min - pre)
            }
            pre = b.max() ?? 0
        }
        return maxGap
    
        // var B = A.sorted()
        
        // var m = 0
        // for i in 1..<B.count{
        //     let diff = B[i] - B[i-1]
        //     if m < diff
        //     {
        //         m = diff
        //     }
        // }
        // return m
	}
}

References ​