Leetcode Maximum Gap problem solution

YASH PAL,

In this Leetcode Maximum Gap problem solution we have 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.

Leetcode Maximum Gap problem solution

Problem solution in Python.

class Solution:
    def maximumGap(self, num):
        count = {}
        if len(num) < 2:
            return 0
        for x in num:
            count[x] = 1
        sortedKeys = sorted(count.keys())
        lastKey = -1
        maxGap = 0
        for key in sortedKeys:
            if lastKey < 0:
                lastKey = key
                continue
            if key - lastKey > maxGap:
                maxGap = key - lastKey
            lastKey = key
        return maxGap

Problem solution in Java.

public class Solution {
    public int maximumGap(int[] nums) {
        int N = nums.length;
        if (N<=1) return 0;
        
        radix_sort(nums, 0, N, 31);
        
        int max_gap = 0;
        for (int i=0; i<N-1; i++)
            max_gap = Math.max(max_gap, nums[i+1]-nums[i]);
        return max_gap;
    }
    
    public void radix_sort(int[] nums, int start, int end, int d) {
        if (d<0 || start>=end) return;
        int N = nums.length;
        int l = start;
        for (int i=start; i<end; i++) 
            if( ((nums[i]>>d)&1)==0 ) swap(nums, i, l++);
        
        radix_sort(nums, start, l, d-1);
        radix_sort(nums, l, end, d-1);
    }
    
    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

Problem solution in C++.

int maximumGap(vector& nums) {
int max1=INT_MIN;
if(nums.size()<2)
return 0;
sort(nums.begin(),nums.end());
for(int i=1;i<nums.size();i++){
int k=abs(nums[i-1]-nums[i]);
max1=max(max1,k);
}return max1;
}

Problem solution in C.

int maximumGap(vector& nums)
{
const int n = nums.size();

if(n < 2) return 0;

    int minV = nums[0];
int maxV = nums[0];

for(int i = 1; i<n; i++)
{
	minV = min(minV, nums[i]);
	maxV = max(maxV, nums[i]);
}
if (n == 2)
	return abs(nums[0]-nums[1]);

int gap = max(1,(maxV-minV)/(n-1));

vector<int> bucket_min( n, INT_MAX);
vector<int> bucket_max( n, INT_MIN);

for(int i = 0; i < n; i++)
{
	int index = (nums[i] - minV)/gap;
	bucket_min[index] = min(bucket_min[index], nums[i]);
	bucket_max[index] = max(bucket_max[index], nums[i]);
}

int maxGap = 0;
int lastMax = minV;
for(int i = 0; i<n; i++)
{
	if(bucket_min[i]!=INT_MAX)
		maxGap = max(maxGap, bucket_min[i] - lastMax);
	if(bucket_max[i]!=INT_MIN)
		lastMax = bucket_max[i];	
}
return maxGap;
}

coding problems