Simple and concise Python using sorting, O(nlogn)


  • 0
    S

    We first turn hh::mm into minutes representation tm ranging from 0 to 1439, where 00:00=0 and 23:59=1439.

    Then we sort this array in ascending order.

    If the largest difference (i.e., the last one minus the first one tm[-1]-tm[0]) is smaller than half of the circle, that is, 720, then we can easily identify the minimal difference by comparing the difference between each adjacent pair in tm.

    However, if the largest difference is greater than the half of the circle, the true difference between tm[-1] and tm[0] should be tm[0]-tm[-1]+1440. It is easy to find that even if there are another two time points satisfying tm[j] - tm[i] > 720, there always exists tm[i] - tm[j] + 1440 >= tm[0]-tm[-1]+1440 since we have tm[i]>=tm[0] and tm[j]<=tm[-1] in the sorted array tm. Therefore, for the circular case, we only need to consider tm[0]-tm[-1]+1440.

    class Solution(object):
        def findMinDifference(self, timePoints):
            """
            :type timePoints: List[str]
            :rtype: int
            """
            # convert to [0, 1439] min
            tm = []
            for t in timePoints:
                h, m = t.split(':')
                tm.append(int(h) * 60 + int(m))
            # sort in ascending order
            tm.sort()
            # find minimal difference between adjacent elements
            min_diff = 2000
            for i in range(0, len(tm) - 1):
                min_diff = min(min_diff, tm[i + 1] - tm[i])
           # also consider the circular case
            return min(min_diff, tm[0] - tm[-1] + 1440)

Log in to reply
 

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