Python solution with counting sort-- 24 lines


  • -5
    D
    class Solution:
        # @param num, a list of integer
        # @return an integer
        def maximumGap(self, num):
            count = {}
            if len(num) < 2:
                return 0
            
            #In linear time make a "histogram". We don't care how many times each occurs.
            for x in num:
                count[x] = 1
            #Turn keys into an array
            sortedKeys = sorted(count.keys())
            lastKey = -1
            maxGap = 0
            #Find max gap from sorted keys in less than linear time
            for key in sortedKeys:
                if lastKey < 0:
                    lastKey = key
                    continue
                if key - lastKey > maxGap:
                    maxGap = key - lastKey
                lastKey = key
            return maxGap

  • 0
    X

    Would the sort() function in "sortedKeys = sorted(count.keys())" cause more than linear time complexity?


  • 0

    actually, dictionary cannot guarantee O(1) enumeration.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.