Minimum Time Difference

Given an array of HH:MM times, find the least difference.

To view the problem statement, view it on leetcode.

Analysis

A few things were immediately clear. First, there are only 1440 minutes in a day, so there were only 1440 timestamps that could be provided in any array. Further, if a timestamp occurred more than twice in an input array, then the minimum difference was zero.

The strategy I used was to first convert the timestamps into minutes - if the same timestamp appeared after being seen once the minimum difference was \(0\). If no exact matches were found, then adjacent values could be sorted out by iterating through all of the minutes, which would have a constant time complexity.

Solution

The solution does what is described above:

class Solution:
    def evalBest(self, minutes_previous: int, minutes_current: int):
        diff = minutes_current - minutes_previous
        diff = min(diff, minutes_total - diff)
        return diff

    def findMinDifference(self, timePoints: list[str]) -> int:

        visited = set()
        parsed = dict()

        for tp in timePoints:
            # NOTE: ensures constant time.
            if tp in visited:
                return 0

            visited.add(tp)

            str_hrs, str_mins = tp.split(":")
            minutes = (int(str_hrs) * 60) + int(str_mins)
            parsed[minutes] = tp

        # NOTE: Iterate parsed in order. This will take constant time since
        #       there are at most 1440 keys.
        diff_best = minutes_total
        minutes_previous = None
        minutes_first = None

        for minutes in range(minutes_total):
            if minutes not in parsed:
                continue
            elif minutes_previous is None:
                minutes_previous = minutes
                minutes_first = minutes
                continue

            minutes_current = minutes
            if diff_best > (diff := self.evalBest(minutes_previous, minutes_current)):
                diff_best = diff

            minutes_previous = minutes_current

        # NOTE: Order matters since ``abs`` is not applied.
        # NOTE: Compare the first and final entries since the will not be
        #       compared in the above loop.
        if diff_best > (diff := self.evalBest(minutes_first, minutes_current)):  # type: ignore
            diff_best = diff

        return diff_best

and was in the \(95\%\) quantile for runtime and \(79\%\) quantile for memory usage. The time complexity of the solution should be \(O(N^0)\) for the iteration over the minutes, and \(O(N^0) + \epsilon N\) for the parsing part. \(\epsilon\) is the constant time factor for checking tp in visited above, this is constant because visited is a set, which uses hashing. The overall upper bound for the time complexity of this solution is

\[\begin{equation} 2880 + \epsilon N \end{equation}\]

where \(\epsilon\) is really small.

Possible Optimizations

Since this solution did pretty well and I’d like to do another problem I will only speculate that having the local parsed of findMinDifference as a global should help take some of the string parsing time off.

Further, using sorted could make might be fast enough to make it more efficient than using the second for loop.