#164

Medium

LeetCode Problem Workspace

Maximum Gap

Find the largest difference between successive elements in a sorted array efficiently using linear time techniques and bucket strategies.

array sorting bucket sort radix sort

Problem Statement

Given an integer array nums, determine the maximum difference between two consecutive elements after sorting the array in ascending order. If nums contains fewer than two elements, return 0 as no gap exists.

Your algorithm must run in linear time and use linear extra space, making it suitable for large arrays. For example, given nums = [3,6,9,1], the sorted array is [1,3,6,9], yielding a maximum gap of 3.

Examples

Example 1

Input: nums = [3,6,9,1]

Output: 3

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

The array contains less than 2 elements, therefore return 0.

Constraints

1 <= nums.length <= 105
0 <= nums[i] <= 109

Solution Approach

Use Bucket Sort to Partition the Range

Divide the array range into n-1 buckets, where n is the number of elements. Place each number into a bucket based on its value. The maximum gap will occur between non-empty consecutive buckets rather than inside buckets, avoiding full sorting and maintaining linear time.

Compute Gaps Between Buckets

Track the minimum and maximum values in each bucket. Iterate through buckets in order, calculating the difference between the current bucket's minimum and the previous bucket's maximum. Keep the largest difference encountered as the maximum gap.

Handle Edge Cases Carefully

Return 0 if the array length is less than 2. Ensure that empty buckets are skipped when computing gaps. This prevents incorrectly counting gaps where no elements exist and aligns with the problem's constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) using bucket or radix sort, as each element is placed in a bucket once and gaps are computed in a single pass. Space complexity is O(n) due to the buckets used to store min and max values across the array range.

What Interviewers Usually Probe

Expect discussion on linear time sorting alternatives like bucket sort or radix sort.
Clarify how maximum gaps occur between buckets rather than within buckets.
Check edge case handling for arrays with less than two elements or uniform values.

Common Pitfalls or Variants

Common pitfalls

Sorting the array normally violates the linear time constraint and may be penalized.
Failing to skip empty buckets can lead to incorrect maximum gap computation.
Not handling arrays with fewer than two elements results in invalid outputs.

Follow-up variants

Find the maximum difference in a circularly sorted array using the same bucket principles.
Compute the maximum gap when numbers can be negative or very large, requiring careful bucket range calculation.
Apply a similar approach to floating-point arrays by scaling values into discrete buckets.

FAQ

What is the main approach to solve Maximum Gap efficiently?

Use bucket sort or radix sort to partition the array and compute the maximum difference between consecutive non-empty buckets.

Can I just sort the array normally for Maximum Gap?

Normal sorting works logically but does not meet the linear time requirement. Bucket or radix sort preserves O(n) time complexity.

How do I handle arrays with fewer than two elements?

Return 0, since there are no consecutive elements to form a gap, consistent with problem constraints.

Why is the maximum gap always between buckets, not inside a bucket?

Because each bucket holds a subrange, any gap within a bucket is smaller than the gap between buckets due to range partitioning.

Does GhostInterview provide hints specific to the array plus sorting pattern?

Yes, it focuses on identifying pattern matches and guiding toward bucket or radix sorting strategies for correct gap calculation.

terminal

Solution

Solution 1: 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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return 0
        mi, mx = min(nums), max(nums)
        bucket_size = max(1, (mx - mi) // (n - 1))
        bucket_count = (mx - mi) // bucket_size + 1
        buckets = [[inf, -inf] for _ in range(bucket_count)]
        for v in nums:
            i = (v - mi) // bucket_size
            buckets[i][0] = min(buckets[i][0], v)
            buckets[i][1] = max(buckets[i][1], v)
        ans = 0
        prev = inf
        for curmin, curmax in buckets:
            if curmin > curmax:
                continue
            ans = max(ans, curmin - prev)
            prev = curmax
        return ans

Continue Practicing

#912 sort an array #220 contains duplicate iii #347 top k frequent elements