Leetcode Daily Question 16/09/2024 - 539. Minimum Time Difference

Problem Description:

Given a list of 24-hour clock time points in "HH:MM" format, return the minimum minutes difference between any two time-points in the list. Note that the question is NOT order sensitive. So (00:00, 23:59) has the same time difference as (23:59, 00:00)

from typing import List
import itertools
class Solution:
  def timeToMins(self, time: str) -> int:
    return int(time[:2]) * 60 + int(time[3:])
  
  def findMinDifference(self, timePoints: List[str]) -> int:
    time_mins = [self.timeToMins(time) for time in timePoints]
    time_mins.sort()
    first = time_mins[0]
    last = time_mins[-1]
    min_time = 1440 + first - last
    for i, j in itertools.pairwise(time_mins):
      diff = j - i
      if min_time > diff:
        min_time = diff
    
    return min_time

Explanation:

We can solve this by changing all the times into time from midnight (clockwise), sorting it and comparing each of the pairs to find the minimum difference.

It is worth noting that that time is circular, so we need to compare the first and last time to check if the smallest anticlockwise distance between times is the smallest difference.

We first define a function to change all the times in timePoints into minutes from midnight.

def timeToMins(time):
  return int(time[:2]) * 60 + int(time[3:])

Then, we convert all times in timePoints into mins from midnight and sort using the built-in sort function.

time_mins = [timeToMins(time) for time in timePoints]
time_mins.sort()

After that, we initiate min_time variable by calculating the closest anticlockwise distance.

first = time_mins[0]
last = time_mins[-1]
min_time = 1440 + first - last

Lastly, we use the pairwise method in the itertools module to compare each pair of times against our min_time.

for i, j in itertools.pairwise(time_mins):
  diff = j - i
  if diff < min_time:
    min_time = diff

return min_time

This has time complexity O(n log n). This is because of the sort() method. This pseudo quick sort method has time complexity O(n log n). Iterating through time_mins takes O(n) time (both when creating time_mins and calculating using it).

This has space complexity O(n). This is because we need to store time_mins which has the same size as timePoints.

The full solution can be found near the top of the page.