#164 Maximum Gap - Solution

The key challenge in #164 Maximum Gap is to find the maximum difference between adjacent elements in the sorted order of an array, without explicitly sorting it in O(n log n) time. A common optimization uses the Pigeonhole Principle with a bucket-based strategy.

First, identify the global min and max values. If there are n elements, the minimum possible maximum gap must be at least (max - min) / (n - 1). This observation allows us to divide the range into buckets where each bucket stores only the minimum and maximum value encountered. Since the maximum gap cannot occur inside a bucket, we only compare the boundaries between consecutive non-empty buckets.

This approach avoids full sorting and achieves near-linear performance. Alternatively, Radix Sort can also be used to sort numbers in linear time before computing adjacent differences. The bucket-based technique typically yields O(n) time with O(n) extra space.

Approach	Time Complexity	Space Complexity
Bucket-Based Gap Calculation	O(n)	O(n)
Radix Sort + Scan	O(n)	O(n)
Standard Sorting + Scan	O(n log n)	O(1) to O(n)

Solutions (12)

Sorting Approach

The simplest approach to solve this problem is to first sort the array. Once sorted, the maximum gap will be found between consecutive elements. By iterating over the sorted array and computing the difference between each pair of consecutive elements, we can find the maximum difference.

Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(1) as no additional space is used except for variables.

C C++Java Python C#JavaScript

1using System;
2
3public class Solution {
4    public int MaximumGap(int[] nums) {
5        if (nums.Length < 2) return 0;
6        Array.Sort(nums);
7        int maxGap = 0;
8        for (int i = 1; i < nums.Length; i++) {
9            maxGap = Math.Max(maxGap, nums[i] - nums[i - 1]);
10        }
11        return maxGap;
12    }
13}

Explanation

C#'s Array.Sort is used to sort the numbers. The algorithm then computes the maximum difference between consecutive sorted numbers.

Bucket Sort Approach

This approach leverages the bucket sort idea to achieve linear time complexity. By calculating the bucket size and distributing array elements across buckets, we attempt to isolate maximum differences across distinct buckets, as adjacent elements within a bucket should have a smaller difference.

Time Complexity: O(n) since the bucket placement and scanning are linear operations.
Space Complexity: O(n) for the two bucket arrays.

C C++Java Python C#JavaScript

1#include <vector>
#include <algorithm>
#include <limits>

int maximumGap(std::vector<int>& nums) {
    if (nums.size() < 2) return 0;
    int minVal = *std::min_element(nums.begin(), nums.end());
    int maxVal = *std::max_element(nums.begin(), nums.end());
    int bucketSize = std::max(1, (maxVal - minVal) / ((int)nums.size() - 1));
    int bucketCount = (maxVal - minVal) / bucketSize + 1;
    std::vector<int> minBucket(bucketCount, std::numeric_limits<int>::max());
    std::vector<int> maxBucket(bucketCount, std::numeric_limits<int>::min());
    for (int num : nums) {
        int idx = (num - minVal) / bucketSize;
        minBucket[idx] = std::min(minBucket[idx], num);
        maxBucket[idx] = std::max(maxBucket[idx], num);
    }
    int maxGap = 0, prev = minVal;
    for (size_t i = 0; i < minBucket.size(); ++i) {
        if (minBucket[i] == std::numeric_limits<int>::max()) continue;
        maxGap = std::max(maxGap, minBucket[i] - prev);
        prev = maxBucket[i];
    }
    return maxGap;
}