Question

Formatted question description: https://leetcode.ca/all/164.html

 164	Maximum Gap

 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.

 Example 1:

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

 Note:

 You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.
 Try to solve it in linear time/space.

 @tag-math

Algorithm

Bucket Sort is used to do it. First, find the maximum and minimum values of the array, and then determine the capacity of each bucket, which is (maximum-minimum) / number + 1. When determining the number of buckets, that is (maximum-minimum) / the capacity of the bucket + 1,

Then you need to find the local maximum and minimum in each bucket, and the two numbers with the maximum distance will not be in the same bucket, but the distance between the minimum value of one bucket and the maximum value of another bucket.

  • This is because all numbers should be evenly distributed to each bucket as much as possible, rather than crowded in one bucket, which ensures that the maximum and minimum values will not be in the same bucket

Code

Java

public class Maximum_Gap {

    public class Solution {
        public int maximumGap(int[] nums) {
            if (nums == null || nums.length <= 1) {
                return 0;
            }

            // Step 1: find max and min element
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            for (int num : nums) {
                if (num > max) {
                    max = num;
                }

                if (num < min) {
                    min = num;
                }
            }

            int len = nums.length;

            // Step 2: calculate the intervals and number of buckets.
            int interval = (int) Math.ceil((double) (max - min) / (len - 1));

            if (interval == 0) {
                interval = 1;
            }
            int numBuckets = (max - min) / interval + 1;
            Bucket[] buckets = new Bucket[numBuckets];
            for (int i = 0; i < numBuckets; i++) {
                buckets[i] = new Bucket();
            }

            // Step 3: iterate through the nums and assign the number into the buckets.
            for (int num : nums) {
                int bucketNum = (num - min) / interval;
                if (num > buckets[bucketNum].max) {
                    buckets[bucketNum].max = num;
                }

                if (num < buckets[bucketNum].min) {
                    buckets[bucketNum].min = num;
                }
            }

            // Step 4: iterate through the buckets and get the maximal gap
            int prev = buckets[0].max;
            int maxGap = 0;
            for (int i = 1; i < numBuckets; i++) {
                if (prev != Integer.MIN_VALUE && buckets[i].min != Integer.MAX_VALUE) {
                    maxGap = Math.max(maxGap, buckets[i].min - prev);
                    prev = buckets[i].max;
                }
            }

            return maxGap;
        }

        private class Bucket {
            public int min;
            public int max;

            public Bucket() {
                min = Integer.MAX_VALUE;
                max = Integer.MIN_VALUE;
            }
        }
    }

}

All Problems

All Solutions