leetcode hard : Maximum Gap

https://leetcode.com/problems/maximum-gap/description/

Maximum Gap - LeetCode

 

이 문제는 Bucket Sort를 알아야 풀 수 있다.

버킷 정렬이란? https://hroad.tistory.com/25

[알고리즘] 버킷 정렬 (Bucket Sort)

 

모범 풀이를 보자

class Solution:
    def maximumGap(self, nums):
        lo, hi, n = min(nums), max(nums), len(nums)
        if n <= 2 or hi == lo: return hi - lo
        B = defaultdict(list)
        for num in nums:
            ind = n-2 if num == hi else (num - lo)*(n-1)//(hi-lo)
            B[ind].append(num)
            
        cands = [[min(B[i]), max(B[i])] for i in range(n-1) if B[i]]
        return max(y[0]-x[1] for x,y in zip(cands, cands[1:]))

먼저 max값과 min값을 구한다. 그리고 그 gap을 구해보자.

여기서 확실한게 하나 생긴다.

maximum gap은 언제 최소일까? 숫자가 균일하게 분포되어 있을때다.

(max - min) / (N - 1) 근처일 것이다.

예를 들어 min이 1이고 max가 5

1과 5 사이에 gap이 (N - 1)개 생길것이다.

N이 3이라면

1 3 5

1-3, 3-5 이렇게 gap이 2개(N-1) 생겼다.

이때 maximum gap은 2다. (max - min) / (N - 1)

N이 4라면?

1 2 4 5

maximum gap은 똑같이 2다. ceil( (max - min) / (N - 1) )

 

즉 maximum gap의 최소값은 ceil( (max - min) / (N - 1) ) 이다.

bucket size를 ceil( (max - min) / (N - 1) )보다 작게하면 그 안에 있는 숫자의 차가 maximum gap이 될 일은 없다.

그럼 각 bucket들과의 비교만 하면 되는것이다. 앞 버킷의 max값과 뒷 버킷의 min값의 차를 구해서 그중 최대값을 구하면 되고

이게 위 코드의 마지막 두 줄이다.

cands = [[min(B[i]), max(B[i])] for i in range(n-1) if B[i]]
return max(y[0]-x[1] for x,y in zip(cands, cands[1:]))

 

다른 사람 풀이를 하나 더 보자.

https://leetcode.com/problems/maximum-gap/solutions/1241681/java-python-bucket-idea-with-picture-clean-concise-o-n/?orderBy=most_votes 

[Java/Python] Bucket Idea with Picture - Clean & Concise - O(N) - Maximum Gap - LeetCode

잘 설명돼있다.

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        mi, ma, n = min(nums), max(nums), len(nums)
        if mi == ma: return 0  # All elements are the same
        bucketSize = math.ceil((ma - mi) / (n - 1))
        minBucket = [math.inf] * n
        maxBucket = [-math.inf] * n
        for x in nums:
            idx = (x - mi) // bucketSize
            minBucket[idx] = min(minBucket[idx], x)
            maxBucket[idx] = max(maxBucket[idx], x)

        maxGap = bucketSize  # Maximum gap is always greater or equal to bucketSize
        prev = maxBucket[0]  # We always have 0th bucket
        for i in range(1, n):
            if minBucket[i] == math.inf: continue  # Skip empty bucket
            maxGap = max(maxGap, minBucket[i] - prev)
            prev = maxBucket[i]
        return maxGap

시간복잡도의 공간복잡도는 모두 O(N)