LC 539

Sort
Sort
Publish Date:   2022-02-20

Solution to LeetCode 539 Minimum Time Difference.

LeetCode 539

Minimum Time Difference (Medium). [link]

Sorting and “Pigeonhole Principle”. Time complexity O(N log N). Space complexity O(log N) taken by sorting.

class Solution(object):
    def findMinDifference(self, timePoints):
        """
        :type timePoints: List[str]
        :rtype: int
        """
        def getMinutes(t):
            first_part = ((ord(t[0]) - ord('0')) * 10 + ord(t[1]) - ord('0')) * 60
            second_part = (ord(t[3]) - ord('0')) * 10 + ord(t[4]) - ord('0')
            return first_part + second_part
        
        timePoints.sort()
        MIN = float('inf') # store the minimal
         
        t0 = getMinutes(timePoints[0])
        pre = t0
        
        for i in range(1, len(timePoints)):
            minutes = getMinutes(timePoints[i])
            MIN = min(MIN, minutes - pre) # diff of the neighbors
            pre = minutes
        
        MIN = min(MIN, t0 + 1440 - pre) # diff of the first and the last
        return MIN

Note that there are in total 24*60 = 1440 different Time, so if the length of timePoints is larger than 1440, there must be two duplicated time. In this case, we return 0.

Sort
  TOC