# 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):
= minutes_current - minutes_previous
diff = min(diff, minutes_total - diff)
diff return diff
def findMinDifference(self, timePoints: list[str]) -> int:
= set()
visited = dict()
parsed
for tp in timePoints:
# NOTE: ensures constant time.
if tp in visited:
return 0
visited.add(tp)
= tp.split(":")
str_hrs, str_mins = (int(str_hrs) * 60) + int(str_mins)
minutes = tp
parsed[minutes]
# NOTE: Iterate parsed in order. This will take constant time since
# there are at most 1440 keys.
= minutes_total
diff_best = None
minutes_previous = None
minutes_first
for minutes in range(minutes_total):
if minutes not in parsed:
continue
elif minutes_previous is None:
= minutes
minutes_previous = minutes
minutes_first continue
= minutes
minutes_current if diff_best > (diff := self.evalBest(minutes_previous, minutes_current)):
= diff
diff_best
= minutes_current
minutes_previous
# 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
diff_best
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.