algoadvance

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.

Example:

Input: ["23:59", "00:00"]
Output: 1

Note:

  1. The number of time points in the given list is at least 2 and won’t exceed 20000.
  2. The input time points are in “HH:MM” format.

Clarifying Questions

  1. Q: Can the list of time points include duplicates? A: Yes, duplicates are possible and should be handled appropriately.

  2. Q: Should we consider time between consecutive days, given the 24-hour format? A: Yes. The smallest difference might span across midnight.

Now, let’s move on to the strategy and code.

Strategy

  1. Convert Time to Minutes:
    • Convert each time point from “HH:MM” format to the total minutes past midnight. For example, “00:00” converts to 0 and “23:59” converts to 1439 minutes.
  2. Sort the Times:
    • Sort the list of time points (in minutes). Sorting helps us efficiently find the smallest difference by comparing consecutive elements.
  3. Compute Minimum Difference:
    • Compute differences between adjacent time points in the sorted list.
    • Additionally, check the difference between the last and first time points across midnight (e.g., “23:59” to “00:00”).

Code

Here’s the Python code implementing the above strategy:

def findMinDifference(timePoints):
    # Convert a time string "HH:MM" to minutes past midnight
    def toMinutes(timeString):
        hours, minutes = map(int, timeString.split(':'))
        return hours * 60 + minutes
    
    # Convert all time points to minutes
    minutesList = [toMinutes(time) for time in timePoints]
    
    # Sort the list of minutes
    minutesList.sort()
    
    # Initialize the minimum difference to a large number
    minDiff = float('inf')
    
    # Iterate through the sorted list and find the minimum difference
    for i in range(1, len(minutesList)):
        minDiff = min(minDiff, minutesList[i] - minutesList[i - 1])
    
    # Check the difference between the last and first time points (crossing midnight)
    minDiff = min(minDiff, (minutesList[0] + 1440) - minutesList[-1])
    
    return minDiff

# Example usage
timePoints = ["23:59", "00:00"]
print(findMinDifference(timePoints))  # Output: 1

Time Complexity

  1. Conversion to Minutes: O(n) where n is the number of time points.
  2. Sorting: O(n log n) due to the sort operation.
  3. Finding Minimum Difference: O(n) as we iterate through the sorted list once.

Overall, the time complexity is dominated by the sorting step, making it O(n log n).

This solution is efficient and handles the edge cases such as the transition from “23:59” to “00:00” correctly.

Try our interview co-pilot at AlgoAdvance.com