164. Maximum Gap - Solution & Explanation

The problem

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.

Example 1:

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

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹

Approach overview

Problem Overview: You are given an unsorted integer array. After sorting the array, compute the maximum difference between two consecutive elements. The challenge is solving it efficiently for large inputs where a full comparison-based sort may not be optimal.

Approach 1: Sorting the Array (O(n log n) time, O(1)–O(n) space)

The straightforward approach is to sort the array using a standard sorting algorithm and then scan the sorted result to find the largest gap between adjacent elements. First call the language's built-in sort. Then iterate from index 1 to n-1 and compute nums[i] - nums[i-1], tracking the maximum difference.

This works because once the array is sorted, the maximum adjacent gap must appear between two neighboring values in that order. The implementation is short and reliable since optimized library sorts are highly tuned. Time complexity is O(n log n), and space complexity ranges from O(1) to O(n) depending on the sorting implementation.

This approach is usually acceptable in practice and is easy to explain during interviews. However, the problem specifically encourages a linear-time idea using non-comparison sorting.

Approach 2: Bucket Sort / Pigeonhole Principle (O(n) time, O(n) space)

The optimal solution uses the pigeonhole principle and a variation of bucket sort. Instead of fully sorting the array, compute the global minimum and maximum values first. If there are n numbers, the minimum possible maximum gap must be at least (max - min) / (n - 1). This value determines the bucket size.

Create buckets that each store only two values: the minimum and maximum number placed in that bucket. Iterate through the array and place each value into its bucket using an index like (num - min) / bucketSize. You never store every element inside the bucket—only the local min and max.

The key insight: the maximum gap cannot occur inside a bucket because bucket width is bounded. The real gap appears between the maximum of one bucket and the minimum of the next non-empty bucket. After filling buckets, iterate through them, skipping empty ones, and compute the difference between consecutive bucket boundaries.

This reduces the problem to linear passes over the array and bucket list. Time complexity becomes O(n) with O(n) space. The idea is closely related to distribution-based methods like radix sort and is commonly used when the value range can guide partitioning.

Recommended for interviews: Start with the sorting solution because it clearly demonstrates correctness and problem understanding. Then move to the bucket-based linear solution. Interviewers typically expect candidates to recognize the pigeonhole principle and explain why the maximum gap must occur between buckets rather than inside them.

Approach 1: 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.

Python

class Solution:
    def maximumGap(self, nums):
        if len(nums) < 2:
            return 0
        nums.sort()
        max_gap = 0
        for i in range(1, len(nums)):
            max_gap = max(max_gap, nums[i] - nums[i - 1])
        return max_gap

Java

import java.util.Arrays;

public class Solution {
    public int maximumGap(int[] nums) {
        if (nums.length < 2) return 0;
        Arrays.sort(nums);
        int maxGap = 0;
        for (int i = 1; i < nums.length; i++) {
            maxGap = Math.max(maxGap, nums[i] - nums[i - 1]);
        }
        return maxGap;
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

int maximumGap(std::vector<int>& nums) {
    if (nums.size() < 2) return 0;
    std::sort(nums.begin(), nums.end());
    int maxGap = 0;
    for (size_t i = 1; i < nums.size(); ++i) {
        maxGap = std::max(maxGap, nums[i] - nums[i - 1]);
    }
    return maxGap;
}

JavaScript

function maximumGap(nums) {
    if (nums.length < 2) return 0;
    nums.sort((a, b) => a - b);
    let maxGap = 0;
    for (let i = 1; i < nums.length; i++) {
        maxGap = Math.max(maxGap, nums[i] - nums[i - 1]);
    }
    return maxGap;
}

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int maximumGap(int* nums, int numsSize) {
    if (numsSize < 2) return 0;
    qsort(nums, numsSize, sizeof(int), compare);
    int maxGap = 0;
    for (int i = 1; i < numsSize; i++) {
        int gap = nums[i] - nums[i - 1];
        if (gap > maxGap) maxGap = gap;
    }
    return maxGap;
}

using System;

public class Solution {
    public int MaximumGap(int[] nums) {
        if (nums.Length < 2) return 0;
        Array.Sort(nums);
        int maxGap = 0;
        for (int i = 1; i < nums.Length; i++) {
            maxGap = Math.Max(maxGap, nums[i] - nums[i - 1]);
        }
        return maxGap;
    }
}

In this Python solution, the list is sorted using the sort() method. The maximum difference is calculated by iterating through sorted elements.

Complexity

Time Complexity: O(n log n) due to sort operation.
Space Complexity: O(1) as no additional data structures are used.

Try this approach in the editor

Approach 2: 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.

Python

class Solution:
    def maximumGap(self, nums):
        if len(nums) < 2:
            return 0
        min_val, max_val = min(nums), max(nums)
        bucket_size = max(1, (max_val - min_val) // (len(nums) - 1))
        bucket_count = (max_val - min_val) // bucket_size + 1
        min_bucket = [float('inf')] * bucket_count
        max_bucket = [float('-inf')] * bucket_count
        for num in nums:
            idx = (num - min_val) // bucket_size
            min_bucket[idx] = min(min_bucket[idx], num)
            max_bucket[idx] = max(max_bucket[idx], num)
        max_gap, prev = 0, min_val
        for i in range(bucket_count):
            if min_bucket[i] == float('inf'):
                continue
            max_gap = max(max_gap, min_bucket[i] - prev)
            prev = max_bucket[i]
        return max_gap

Java

import java.util.Arrays;
import java.util.Collections;

public class Solution {
    public int maximumGap(int[] nums) {
        if (nums.length < 2) return 0;
        int minVal = Arrays.stream(nums).min().getAsInt();
        int maxVal = Arrays.stream(nums).max().getAsInt();
        int bucketSize = Math.max(1, (maxVal - minVal) / (nums.length - 1));
        int bucketCount = (maxVal - minVal) / bucketSize + 1;
        Integer[] minBucket = new Integer[bucketCount];
        Integer[] maxBucket = new Integer[bucketCount];
        for (int num : nums) {
            int idx = (num - minVal) / bucketSize;
            if (minBucket[idx] == null || num < minBucket[idx]) minBucket[idx] = num;
            if (maxBucket[idx] == null || num > maxBucket[idx]) maxBucket[idx] = num;
        }
        int maxGap = 0, prev = minVal;
        for (int i = 0; i < bucketCount; i++) {
            if (minBucket[i] == null) continue;
            maxGap = Math.max(maxGap, minBucket[i] - prev);
            prev = maxBucket[i];
        }
        return maxGap;
    }
}

C++

#include <iostream>
#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;
}

JavaScript

function maximumGap(nums) {
    if (nums.length < 2) return 0;
    let minVal = Math.min(...nums);
    let maxVal = Math.max(...nums);
    let bucketSize = Math.max(1, Math.floor((maxVal - minVal) / (nums.length - 1)));
    let bucketCount = Math.floor((maxVal - minVal) / bucketSize) + 1;
    let minBucket = new Array(bucketCount).fill(Infinity);
    let maxBucket = new Array(bucketCount).fill(-Infinity);
    nums.forEach(num => {
        let idx = Math.floor((num - minVal) / bucketSize);
        minBucket[idx] = Math.min(minBucket[idx], num);
        maxBucket[idx] = Math.max(maxBucket[idx], num);
    });
    let maxGap = 0, prev = minVal;
    for(let i = 0; i < bucketCount; i++) {
        if (minBucket[i] === Infinity) continue;
        maxGap = Math.max(maxGap, minBucket[i] - prev);
        prev = maxBucket[i];
    }
    return maxGap;
}

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int maximumGap(int* nums, int numsSize) {
    if (numsSize < 2) return 0;
    int minVal = INT_MAX, maxVal = INT_MIN;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] < minVal) minVal = nums[i];
        if (nums[i] > maxVal) maxVal = nums[i];
    }
    int bucketSize = (maxVal - minVal) / (numsSize - 1) + 1;
    int bucketCount = (maxVal - minVal) / bucketSize + 1;
    int *minBucket = (int*)malloc(bucketCount * sizeof(int));
    int *maxBucket = (int*)malloc(bucketCount * sizeof(int));
    for (int i = 0; i < bucketCount; i++) {
        minBucket[i] = INT_MAX;
        maxBucket[i] = INT_MIN;
    }
    for (int i = 0; i < numsSize; i++) {
        int b = (nums[i] - minVal) / bucketSize;
        if (nums[i] < minBucket[b]) minBucket[b] = nums[i];
        if (nums[i] > maxBucket[b]) maxBucket[b] = nums[i];
    }
    int maxGap = 0, prev = minVal;
    for (int i = 0; i < bucketCount; i++) {
        if (minBucket[i] == INT_MAX) continue;
        maxGap = (maxGap > minBucket[i] - prev) ? maxGap : minBucket[i] - prev;
        prev = maxBucket[i];
    }
    free(minBucket);
    free(maxBucket);
    return maxGap;
}

using System;

public class Solution {
    public int MaximumGap(int[] nums) {
        if (nums.Length < 2) return 0;
        int minVal = nums.Min();
        int maxVal = nums.Max();
        int bucketSize = Math.Max(1, (maxVal - minVal) / (nums.Length - 1));
        int bucketCount = (maxVal - minVal) / bucketSize + 1;
        int[] minBucket = new int[bucketCount];
        int[] maxBucket = new int[bucketCount];
        Array.Fill(minBucket, Int32.MaxValue);
        Array.Fill(maxBucket, Int32.MinValue);
        foreach (int num in nums) {
            int idx = (num - minVal) / bucketSize;
            minBucket[idx] = Math.Min(minBucket[idx], num);
            maxBucket[idx] = Math.Max(maxBucket[idx], num);
        }
        int maxGap = 0, prev = minVal;
        for (int i = 0; i < bucketCount; i++) {
            if (minBucket[i] == Int32.MaxValue) continue;
            maxGap = Math.Max(maxGap, minBucket[i] - prev);
            prev = maxBucket[i];
        }
        return maxGap;
    }
}

The Python solution applies the bucket strategy by establishing a range-based partitioning, analyzing bucket-constrained min and max values, then finding inter-bucket gaps.

Complexity

Time Complexity: O(n), utilizes single-pass bucket allocation.
Space Complexity: O(n), requiring bucket-based partitions.

Try this approach in the editor

Approach 3: Discuss Different Cases

Let m represent the length of string s, and n represent the length of string t. We can assume that m is always greater than or equal to n.

If m-n > 1, return false directly;

Otherwise, iterate through s and t, if s[i] is not equal to t[i]:

If m neq n, compare s[i+1:] with t[i:], return true if they are equal, otherwise return false;
If m = n, compare s[i:] with t[i:], return true if they are equal, otherwise return false.

If the iteration ends, it means that all the characters of s and t that have been iterated are equal, at this time it needs to satisfy m=n+1.

The time complexity is O(m), where m is the length of string s. The space complexity is O(1).

func maximumGap(nums []int) int {
	n := len(nums)
	if n < 2 {
		return 0
	}
	inf := 0x3f3f3f3f
	mi, mx := inf, -inf
	for _, v := range nums {
		mi = min(mi, v)
		mx = max(mx, v)
	}
	bucketSize := max(1, (mx-mi)/(n-1))
	bucketCount := (mx-mi)/bucketSize + 1
	buckets := make([][]int, bucketCount)
	for i := range buckets {
		buckets[i] = []int{inf, -inf}
	}
	for _, v := range nums {
		i := (v - mi) / bucketSize
		buckets[i][0] = min(buckets[i][0], v)
		buckets[i][1] = max(buckets[i][1], v)
	}
	ans := 0
	prev := inf
	for _, bucket := range buckets {
		if bucket[0] > bucket[1] {
			continue
		}
		ans = max(ans, bucket[0]-prev)
		prev = bucket[1]
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sorting Approach	Time Complexity: O(n log n) due to sort operation. Space Complexity: O(1) as no additional data structures are used.
Bucket Sort Approach	Time Complexity: O(n), utilizes single-pass bucket allocation. Space Complexity: O(n), requiring bucket-based partitions.
Discuss Different Cases	–

Complexity analysis

Approach	Time	Space	When to Use
Sorting the Array	O(n log n)	O(1)–O(n)	Simple implementation using built-in sort. Good when constraints are moderate.
Bucket Sort (Pigeonhole Principle)	O(n)	O(n)	Optimal solution when linear time is required and value range can define buckets.

Frequently asked questions

Is Maximum Gap easy or hard?

Maximum Gap is generally considered a medium-level problem. The sorting solution is easy to implement, but recognizing the linear-time bucket strategy requires deeper understanding of distribution-based sorting and gap analysis.

Maximum Gap Python/Java solution

In Python or Java, the straightforward implementation sorts the array and scans adjacent elements to compute the largest difference. The optimized version creates bucket arrays for minimum and maximum values and performs linear scans to determine the maximum inter-bucket gap.

How to solve Maximum Gap in O(n)?

Compute the global minimum and maximum values, then determine the bucket size using (max - min) / (n - 1). Create buckets that store only the minimum and maximum values for each range. After distributing numbers into buckets, scan across buckets and compute gaps between consecutive non-empty buckets to find the maximum.

What is the best approach for Maximum Gap?

The optimal approach uses bucket sort based on the pigeonhole principle. Instead of sorting all elements, it distributes numbers into buckets using the expected minimum gap size. The maximum difference is then computed between the maximum of one bucket and the minimum of the next non-empty bucket. This achieves O(n) time and O(n) space.

Is Maximum Gap asked at Google/Amazon/Meta?

Maximum Gap appears in interview preparation lists for companies like Amazon, Google, and other large tech firms because it tests understanding of bucket-based sorting and the pigeonhole principle. It is commonly used to evaluate whether candidates can move beyond standard comparison sorting.

What data structure is used in Maximum Gap?

The optimal solution uses an array of buckets where each bucket stores two values: a minimum and maximum element. This structure allows the algorithm to track boundary values efficiently without storing every element in sorted order.

What is the time complexity of Maximum Gap?

The simplest solution sorts the array and scans for the largest adjacent difference, which takes O(n log n) time. The optimal bucket-based approach runs in O(n) time because it performs a few linear passes over the array and bucket list.

Maximum Gap solution and explanation

The problem

Approach overview

Approach 1: Sorting Approach

Approach 2: Bucket Sort Approach

Approach 3: Discuss Different Cases

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Gap solution and explanation

The problem

Approach overview

Approach 1: Sorting Approach

Approach 2: Bucket Sort Approach

Approach 3: Discuss Different Cases

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems