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 <= 1050 <= nums[i] <= 109Problem Overview: You are given an unsorted array of non‑negative integers. After sorting the numbers, compute the largest difference between any two consecutive elements. The challenge is solving it faster than a full comparison sort when possible.
Approach 1: Sorting (O(n log n) time, O(1) or O(n) space)
The simplest strategy is to sort the array first. Once sorted, iterate once through the array and compute nums[i] - nums[i-1] for every pair of adjacent elements, keeping track of the maximum difference. This uses built‑in sorting such as quicksort, mergesort, or Timsort depending on the language runtime. It is easy to implement and perfectly acceptable for moderate input sizes. You mainly perform two operations: sort the array, then run a single linear scan to compute the maximum gap.
Approach 2: Bucket Sort / Pigeonhole Principle (O(n) time, O(n) space)
The optimal approach avoids full sorting by using buckets based on the pigeonhole principle. First compute the global min and max values in the array. The minimum possible maximum gap must be at least ceil((max - min) / (n - 1)). Use this value as the bucket size and distribute numbers into buckets storing only the bucket's minimum and maximum. The key insight: the maximum gap will never occur inside a bucket, only between buckets. After filling buckets, iterate across them and compute the difference between the current bucket's minimum and the previous non-empty bucket's maximum. This achieves linear time because each element is placed into a bucket once and the buckets are scanned once.
This approach relies on properties of arrays and non-comparison sorting techniques such as bucket sort. It avoids comparing every pair of elements like traditional sorting algorithms.
Recommended for interviews: Start with the sorting approach to show a clear baseline solution. Interviewers typically expect the bucket-based linear solution because the problem explicitly asks for better than O(n log n) time. Explaining why the maximum gap must occur between buckets demonstrates strong algorithmic reasoning.
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.
This C solution sorts the input array using the built-in qsort function. After sorting, it iterates over the array to calculate the maximum difference between successive elements.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(1) as no additional space is used except for variables.
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.
This C solution calculates the bucket size based on the range of numbers and the number of elements in the array. Elements are then placed into buckets which are used to determine the maximum gap between non-empty buckets.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) since the bucket placement and scanning are linear operations.
Space Complexity: O(n) for the two bucket arrays.
| Approach | Complexity |
|---|---|
| Sorting Approach | Time Complexity: O(n log n) due to the sorting step. |
| Bucket Sort Approach | Time Complexity: O(n) since the bucket placement and scanning are linear operations. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting | O(n log n) | O(1) to O(n) | Simplest implementation using built-in sorting. Good when constraints are moderate or interview does not require linear time. |
| Bucket Sort (Pigeonhole Principle) | O(n) | O(n) | Optimal solution when the problem requires better than O(n log n) time. Uses buckets to avoid full sorting. |
| Radix + Bucket Style Sorting | O(n) | O(n) | Works when integers have bounded digit length and you want linear-time non-comparison sorting. |
Top K Frequent Elements - Bucket Sort - Leetcode 347 - Python • NeetCode • 665,789 views views
Watch 9 more video solutions →Practice Maximum Gap with our built-in code editor and test cases.
Practice on FleetCode