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.

Examples

Example 1:

1
2
3

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:

1
2
3

Input: nums = [10]
Output: 0
Explanation: The array contains less than 2 elements, therefore return 0.

Similar Problems

Maximum Difference between two elements in array

Solution

Method 1 - Naive approach using Sorting

Here is the approach:

  1. If the length of the array is less than 2, return 0.
  2. Sort the array.
  3. Initialize a variable to store the maximum difference (max_diff).
  4. Iterate through the sorted array, computing the difference between each pair of successive elements and updating max_diff.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public class Solution {
    public int maximumGap(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        Arrays.sort(nums);
        int maxDiff = 0;
        for (int i = 1; i < nums.length; i++) {
            maxDiff = Math.max(maxDiff, nums[i] - nums[i - 1]);
        }
        return maxDiff;
    }
}
1
2
3
4
5
6
7
8

def maximum_gap(nums):
    if len(nums) < 2:
        return 0
    nums.sort()
    max_diff = 0
    for i in range(1, len(nums)):
        max_diff = max(max_diff, nums[i] - nums[i - 1])
    return max_diff

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(1)

Method 2 - Using bucketsort and pigeonhole principle

Using counting sort or radix sort can be effective if the integer range is known and small relative to the size of the array, but these methods are impractical for unknown or very large ranges.

By considering that an array of n numbers in a contiguous sequence has a maximum gap of one, we can infer that real-world scenarios with missing numbers create gaps. Identifying these missing ranges efficiently allows us to solve this problem in O(n) time.

The strategy is to divide the values between the given array’s minimum and maximum values into equally-sized buckets. The goal is to ensure that at least one bucket remains empty. An empty bucket indicates a gap equal to the difference between the maximum value of the previous non-empty bucket and the minimum value of the next non-empty bucket. This is based on the Pigeonhole Principle, which asserts that placing n-1 numbers into n buckets guarantees at least one empty bucket.

Below is a linear-time algorithm for computing the maximum gap, enabling constant time computation: Given a set S of n > 2 real numbers x1, x2, ..., xn:

  1. If the length of the array is less than 2, return 0.
  2. Find the maximum, x_max, and the minimum, x_min, in S.
  3. Divide the interval [x_min, x_max] into (n-1) “buckets” of equal size δ = (x_max - x_min) / (n-1).
  4. For each of the remaining n-2 numbers, determine in which bucket it falls using the floor function. The number xi belongs to the k-th bucket Bk if, and only if, ⌊(xi - x_min) / δ⌋ = k-1.
  5. For each bucket Bk, compute xk_min and xk_max among the numbers that fall in Bk. If the bucket is empty, return nothing. If the bucket contains only one number, return that number as both xk_min and xk_max.
  6. Construct a list L of all the ordered minima and maxima: L: (x1_min, x1_max), (x2_min, x2_max), ..., (x(n-1)_min, x(n-1)_max). Note: Since there are n-1 buckets and only n-2 numbers, by the Pigeonhole Principle, at least one bucket must be empty. Therefore, the maximum distance between a pair of consecutive points must be at least the length of the bucket. Consequently, the solution is not found among a pair of points that are contained in the same bucket.
  7. In L, find the maximum distance between a pair of consecutive minimum and maximum (xi_max, xj_min), where j > i.
  8. Exit with this number as the maximum gap.

Example

For instance, given nums = [5, 3, 1, 8, 9, 2, 4]:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

 nums = [5, 3, 1, 8, 9, 2, 4], n = 7
 1. Min = 1, Max = 9
 2. Create 6 buckets (7-1) with equal size δ = (9-1)/(7-1) = 1.33
 3. Place the remaining elements into the appropriate buckets using the formula (nums[i] - Min)/δ.
 Calculate min and max for each bucket:
  b0    b1    b2    b3    b4    b5
  ____________________________________
  |_2___|__3__|__4__|__5__|______|__8__|
  ^     ^     ^     ^     ^      ^     ^
  1    2.33   3.66  5    6.33   7.66   9
 
 For example, for nums[0] = 5, the bucket number = (nums[0] - Min)/δ = (5 - 1) / 1.33 = 3 => b3
 
 Note: b4 is empty.
 
 4. Identify empty buckets (gaps) and compute the gap value as the difference between the max of the previous non-empty bucket and the min of the next non-empty bucket.
 For instance, b4 is empty, the previous non-empty bucket is b3, and the next non-empty bucket is b5.
 Thus, the gap value at b4 = min(b5) - max(b3) = 8 - 5 = 3.
 5. Update a global maximum and iterate over all empty buckets to perform the gap calculation.
 
 Since there is one empty bucket, the maximum gap is 3.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

public class Solution {
    public int maximumGap(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }

        int minNum = Integer.MAX_VALUE;
        int maxNum = Integer.MIN_VALUE;

        for (int num : nums) {
            minNum = Math.min(minNum, num);
            maxNum = Math.max(maxNum, num);
        }

        if (minNum == maxNum) {
            return 0;
        }

        int n = nums.length;
        int bucketSize = Math.max(1, (maxNum - minNum) / (n - 1));
        int bucketCount = (maxNum - minNum) / bucketSize + 1;

        int[] bucketsMin = new int[bucketCount];
        int[] bucketsMax = new int[bucketCount];

        Arrays.fill(bucketsMin, Integer.MAX_VALUE);
        Arrays.fill(bucketsMax, Integer.MIN_VALUE);

        for (int num : nums) {
            int bucketIdx = (num - minNum) / bucketSize;
            bucketsMin[bucketIdx] = Math.min(bucketsMin[bucketIdx], num);
            bucketsMax[bucketIdx] = Math.max(bucketsMax[bucketIdx], num);
        }

        int maxGap = 0;
        int prevMax = minNum;

        for (int i = 0; i < bucketCount; i++) {
            if (bucketsMin[i] == Integer.MAX_VALUE) {
                continue;
            }
            maxGap = Math.max(maxGap, bucketsMin[i] - prevMax);
            prevMax = bucketsMax[i];
        }

        return maxGap;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def maximum_gap(nums):
    if len(nums) < 2:
        return 0

    min_num, max_num = min(nums), max(nums)
    if min_num == max_num:
        return 0

    n = len(nums)
    bucket_size = max(1, (max_num - min_num) // (n - 1))
    bucket_count = (max_num - min_num) // bucket_size + 1

    buckets_min = [float("inf")] * bucket_count
    buckets_max = [float("-inf")] * bucket_count

    for num in nums:
        bucket_idx = (num - min_num) // bucket_size
        buckets_min[bucket_idx] = min(buckets_min[bucket_idx], num)
        buckets_max[bucket_idx] = max(buckets_max[bucket_idx], num)

    max_gap = 0
    prev_max = min_num

    for i in range(bucket_count):
        if buckets_min[i] == float("inf"):
            continue
        max_gap = max(max_gap, buckets_min[i] - prev_max)
        prev_max = buckets_max[i]

    return max_gap

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)