Maximum Gap | Leetcode

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Credits:
Special thanks to @porker2008 for adding this problem and creating all test cases.

---

Solution: Use bucket sort, but within each bucket, we only need to keep the min and max values. After sorting, iterate through the buckets. The maximum gap is the max of (bucket.max - bucket.min), or (bucket.min - prevBucket.max), where prevBucket is the last bucket which has any elements in it (i.e. not null).

public class Solution {
    private static class Bucket {
        private int min = Integer.MAX_VALUE;
        private int max = Integer.MIN_VALUE;
        
        private void add(int n) {
            min = Math.min(min, n);
            max = Math.max(max, n);
        }
    }
    
    public int maximumGap(int[] nums) {
        if (nums.length < 2) return 0;
        
        // Find min and max.
        int min = IntStream.of(nums).min().getAsInt();
        int max = IntStream.of(nums).max().getAsInt();
        
        // Bucket sort.
        int gap = (max - min + nums.length) / nums.length;
        Bucket[] buckets = new Bucket[nums.length];
        
        for (int n: nums) {
            int b = (n - min) / gap;
            if (buckets[b] == null) buckets[b] = new Bucket();
            buckets[b].add(n);
        }
        
        // Find max gap.
        int maxGap = 0;
        int prevMax = 0;
        
        for (Bucket b: buckets) {
            if (b == null) continue;
            maxGap = Math.max(maxGap, b.max - b.min);
            if (prevMax > 0) maxGap = Math.max(maxGap, b.min - prevMax);
            prevMax = b.max;
        }
        
        return maxGap;
    }
}