Maximum Gap LeetCode solution in Python

1
class Solution:
2
    def maximumGap(self, nums: List[int]) -> int:
3
        if len(nums) < 2:
4
            return 0
5

6
        # radix sort
7
        # N = length of nums
8
        # find number of digits in largest number - O(K) where K = length of largest number
9
        longest = 0
10
        for i in nums:
11
            longest = max(longest, len(str(i)))
12

13
        # normalize so that all numbers have same number of digits by adding 0s at the start of shorter numbers - O(N*K)
14
        for i in range(len(nums)):
15
            if len(str(nums[i])) != longest:
16
                nums[i] = "0" * (longest - len(str(nums[i]))) + str(nums[i])
17
            else:
18
                nums[i] = str(nums[i])
19

20
        # apply counting sort starting with each digit from the end of the last digits - O(K*N)
21
        for digit in range(longest - 1, -1, -1):
22
            vals = [[] for k in range(10)]
23
            for num in nums:
24
                vals[int(num[digit])] += [num]
25
            # join list sorted by that digit position together:
26
            new = []
27
            for i in vals:
28
                new += i
29
            nums = new.copy()
30

31
        # find the largest difference in the now sorted nums - O(N)
32
        best_diff = 0
33
        for i in range(1, len(nums)):
34
            best_diff = max(best_diff, int(nums[i]) - int(nums[i - 1]))
35
        return best_diff
36

37

38
# Overall complexity is O(N*K) but K is at most 10 so O(10*N) = O(N) so linear
39
# Please correct me if I am wrong!