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
1 <= |A| <= 10^6
1 <= Ai <= 10^9

Input Format

The first argument is an integer array A.
The first argument is an integer array A.

Output Format

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

Example Input

A = [1, 10, 5]
A = [1, 10, 5]

Example Output

5
5

Example Explanation

The maximum difference is between 5 and 10, which is 5.
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
	}
}
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 ​