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 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.
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.
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.
Time Complexity: O(n) since the bucket placement and scanning are linear operations.
Space Complexity: O(n) for the two bucket arrays.
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]:
m neq n, compare s[i+1:] with t[i:], return true if they are equal, otherwise return false;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).
| 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. |
| Discuss Different Cases | — |
| 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. |
Maximum Gap | Leetcode 164 | Live coding session | Leetcode Hard • Coding Decoded • 15,958 views views
Watch 9 more video solutions →Practice Maximum Gap with our built-in code editor and test cases.
Practice on FleetCode