Maximum Gap — LeetCode 164 Python Solution
MediumArrayBucket SortRadix SortSorting
- Problem
- #164
- Pattern
- Sorting
- Reading time
- 4 min
- Source
- leetcode.com
The 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.
Example
- 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.
Python solution
Python
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 ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(m), where m is the length of string s |
| Space | O(1) auxiliary |
Pattern: Sorting
Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 164. Maximum Gap is filed here because LeetCode tags it Sorting, Bucket Sort and Radix Sort, which is the vocabulary this hub collects.
The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 164. Maximum Gap?
- LeetCode 164. Maximum Gap is rated Medium on LeetCode.
- What is the time complexity of LeetCode 164. Maximum Gap?
- The Python solution on this page runs in O(m), where m is the length of string s.
- What is the space complexity of LeetCode 164. Maximum Gap?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 164. Maximum Gap cover?
- LeetCode 164. Maximum Gap is tagged Array, Bucket Sort, Radix Sort and Sorting on LeetCode.