python sort & bucket solution


  • 1
    Z

    because there are only 1440 buckets, so the length limit of 20000 is useless.

    sort solution

    class Solution(object):
        def findMinDifference(self, timePoints):
            """
            :type timePoints: List[str]
            :rtype: int
            """
            if len(timePoints) > 1440:
                return 0
            s = sorted(map(lambda t: int(t[:2]) * 60 + int(t[3:]), timePoints))
            return min(s2 - s1 for s1, s2 in zip(s, s[1:] + [1440+s[0]]))
    

    bucket solution

    class Solution(object):
        def findMinDifference(self, timePoints):
            """
            :type timePoints: List[str]
            :rtype: int
            """
            if len(timePoints) > 1440:
                return 0
            buckets = [0] * 1440
            for tp in timePoints:
                seconds = int(tp[:2]) * 60 + int(tp[3:])
                buckets[seconds] += 1
                if buckets[seconds] > 1:
                    return 0
            s = [i for i, cnt in enumerate(buckets) if cnt]
            return min(s2 - s1 for s1, s2 in zip(s, s[1:] + [1440 + s[0]]))
    

  • 0
    L

    Little confused as to why you even have the second solution given that the sort would still be O(1) technically. You should look at the top bucket solution to see what that looks like. Your solution is "count sort" Also you're dealing with minutes not seconds


Log in to reply
 

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