Maximum Gap
Problem Description
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 <= 105
- 0 <= nums[i] <= 109
Solve it on LeetCode
Approaches
1. Simple Sort and Compare
Intuition:
The simplest way to solve this problem is to sort the array and then find the maximum gap between successive elements. Although this is not the most optimal solution in terms of time complexity, it is straightforward to implement and understand.
Steps:
- Sort the given array.
- Initialize a variable
maxGapto store the maximum difference found. - Iterate through the sorted array and calculate the difference between successive elements.
- Update
maxGapif a larger difference is found.
Code:
- Time Complexity: O(N log N) due to sorting the array.
- Space Complexity: O(1) if the sort is done in place.
2. Bucket Sort
Intuition:
To achieve a better time complexity, we can use a bucket sort method. The core idea is distributing the numbers into buckets such that each bucket holds a range of numbers. We calculate the maximum possible difference, which ensures that the maximum gap cannot be confined within a single bucket but must be between the maximum of one bucket and the minimum of the next.
Steps:
- Find the minimum and maximum elements in the array.
- Calculate the gap size, which is the ceiling value of
(max - min) / (n - 1). - Create buckets that will store only the minimum and maximum values that fall into them.
- Iterate through each number to place it in the right bucket by calculating the appropriate index.
- Finally, iterate through the buckets to calculate the maximum gap between the maximum value of the current non-empty bucket and the minimum value of the next non-empty bucket.
Code:
- Time Complexity: O(N) for both average and worst case due to the linear pass to fill buckets and the linear pass to find the maximum gap.
- Space Complexity: O(N) due to the space used for the buckets.