Given an integer array nums, return the maximum difference between two successive elements in its sorted form. If the array contains less than two elements, return 0.

You must write an algorithm that runs in linear time and uses linear extra space.

&nbsp;
Example 1:

Input: nums = [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: nums = [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 105
	0 &lt;= nums[i] &lt;= 109


class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        if len(nums)<2: return 0
        
        #radix sort
        #N = length of nums
        #find number of digits in largest number - O(K) where K = length of largest number
        longest = 0
        for i in nums:
            longest = max(longest,len(str(i)))
            
        #normalize so that all numbers have same number of digits by adding 0s at the start of shorter numbers - O(N*K)
        for i in range(len(nums)):
            if len(str(nums[i]))!=longest:
                nums[i] = '0'*(longest-len(str(nums[i]))) + str(nums[i])
            else:
                nums[i] = str(nums[i])
        
        #apply counting sort starting with each digit from the end of the last digits - O(K*N)
        for digit in range(longest-1,-1,-1):
            vals = [[] for k in range(10)]
            for num in nums:
                vals[int(num[digit])] += [num]
			#join list sorted by that digit position together:
            new = []
            for i in vals:
                new += i
            nums = new.copy()
        
        #find the largest difference in the now sorted nums - O(N)
        best_diff = 0
        for i in range(1,len(nums)):
            best_diff = max(best_diff,int(nums[i])-int(nums[i-1]))
        return best_diff
    
#Overall complexity is O(N*K) but K is at most 10 so O(10*N) = O(N) so linear
#Please correct me if I am wrong!
class Solution {
    public int maximumGap(int[] nums) {
        Arrays.sort(nums);
        int res=0;
        if(nums.length==0){
            return 0;
        }
        for (int i =0;i<nums.length-1;i++){
            res=Math.max(Math.abs(nums[i]-nums[i+1]),res);
        }
        return res;
    }
}
class Solution {
public:
    int maximumGap(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int res;
        int maxx=INT_MIN;
        map<int,int> m;
        if(nums.size()==1)
            return 0;
        for(int i =0;i<nums.size()-1;i++)
        {
            m[i]=nums[i+1]-nums[i];
        }
        for(auto it: m)
        {
            if(it.second>maxx)
            {
                maxx=it.second;
            }
        }
        return maxx;
    }
};
/**
 * The buckets solution.
 *
 * Time Complexity: O(n)
 * Space Complexity: O(n)
 *
 * @param {number[]} nums
 * @return {number}
 */
var maximumGap = function(nums) {
    const n = nums.length

    if (n < 2) {
        return 0
    }

    if (n < 3) {
        return Math.abs(nums[0] - nums[1])
    }

    let maxNum = -Infinity
    let minNum = +Infinity

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

    if (maxNum === minNum) {
        return 0
    }

    const k = n - 1
    const averageGap = (maxNum - minNum) / k

    const minBuckets = new Array(k)
    const maxBuckets = new Array(k)

    minBuckets[0] = minNum
    maxBuckets[0] = minNum

    minBuckets[k - 1] = maxNum
    maxBuckets[k - 1] = maxNum

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

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

        minBuckets[j] = minBuckets[j] ? Math.min(minBuckets[j], nums[i]) : nums[i]
        maxBuckets[j] = maxBuckets[j] ? Math.max(maxBuckets[j], nums[i]) : nums[i]
    }

    let largestGap = 0
    let prevMaxIndex = 0

    for (let i = 1; i < n - 1; i++) {
        if (minBuckets[i]) {
            largestGap = Math.max(largestGap, minBuckets[i] - maxBuckets[prevMaxIndex])
        }

        if (maxBuckets[i]) {
            prevMaxIndex = i
        }
    }

    return largestGap
}
Maximum Gap