algoadvance

Leetcode 164. Maximum Gap

Problem Statement

Given an unsorted array, you need to find the maximum difference between the successive elements in its sorted form. Return 0 if the array contains less than two elements.

Example:

Input: [3, 6, 9, 1]
Output: 3

Example:

Input: [10]
Output: 0

Note:

Clarifying Questions

  1. Q: Can the array contain negative numbers? A: Yes, the array can contain negative numbers.

  2. Q: Is the input only composed of integers? A: Yes, the input array is composed only of integers.

  3. Q: Can the input array be empty? A: Yes, the input array can be empty, and the output should be 0 in that case.

Strategy

To solve this problem in linear time (O(n)) and linear space (O(n)), we can utilize the “Bucket Sort” concept. Here’s how we can approach this problem:

  1. Edge Cases:
    • If the input array contains less than two elements, return 0.
  2. Compute Min and Max:
    • Find the minimum and maximum values in the array.
  3. Bucket Creation:
    • Calculate the bucket size as (maxVal - minVal) / (n - 1). The idea is to divide the range [minVal, maxVal] into n - 1 buckets to ensure that the maximum gap is not contained within the same bucket.
  4. Distribute Elements into Buckets:
    • Distribute the elements of the array into these buckets, ensuring that each element goes into the appropriate bucket based on its value.
  5. Calculate Maximum Gap:
    • For each bucket, keep track of the minimum and maximum values. Then, iterate through the buckets to find the maximum gap between the maximum value of the current bucket and the minimum value of the next non-empty bucket.

Code

import java.util.Arrays;

public class MaximumGap {

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

        // Step 1: Find minimum and maximum values in the array
        int minVal = Integer.MAX_VALUE;
        int maxVal = Integer.MIN_VALUE;
        for (int num : nums) {
            minVal = Math.min(minVal, num);
            maxVal = Math.max(maxVal, num);
        }

        // Step 2: Calculate bucket size and initialize buckets
        int n = nums.length;
        int bucketSize = Math.max(1, (maxVal - minVal) / (n - 1));
        int bucketCount = (maxVal - minVal) / bucketSize + 1;
        
        int[] bucketMin = new int[bucketCount];
        int[] bucketMax = new int[bucketCount];
        Arrays.fill(bucketMin, Integer.MAX_VALUE);
        Arrays.fill(bucketMax, Integer.MIN_VALUE);
        
        // Step 3: Put array elements into buckets
        for (int num : nums) {
            int bucketIndex = (num - minVal) / bucketSize;
            bucketMin[bucketIndex] = Math.min(bucketMin[bucketIndex], num);
            bucketMax[bucketIndex] = Math.max(bucketMax[bucketIndex], num);
        }
        
        // Step 4: Calculate the maximum gap
        int maxGap = 0;
        int previousMax = minVal;
        for (int i = 0; i < bucketCount; i++) {
            if (bucketMin[i] == Integer.MAX_VALUE && bucketMax[i] == Integer.MIN_VALUE) {
                // Empty bucket
                continue;
            }
            // maxGap is the difference between the minimal value of the current bucket and the maximum value of the previous bucket
            maxGap = Math.max(maxGap, bucketMin[i] - previousMax);
            previousMax = bucketMax[i];
        }

        return maxGap;
    }
    
    public static void main(String[] args) {
        MaximumGap mg = new MaximumGap();
        System.out.println(mg.maximumGap(new int[]{3, 6, 9, 1}));  // Output: 3
        System.out.println(mg.maximumGap(new int[]{10}));          // Output: 0
    }
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI