https://www.interviewbit.com/problems/max-distance/discussion/p/simplest-way-possible-o-n-time-complexity-and-only-one-auxiliary-array-o-n

maximumGap.py

class Solution:
    # @param A : tuple of integers
    # @return an integer
    def maximumGap(self, A):
        n = len(A)

        nums = []

        for item in enumerate(A):
            nums.append(item)


        def cmp(a):
            return a[1]


        nums.sort(key=cmp)

        max_distance = 0
        min_num = nums[0][0]

        for num in nums:
            if num[0] <= min_num:
                min_num = num[0]
            else:
                max_distance = max(max_distance, num[0] - min_num)
        return max_distance