We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Time Difference

Difficulty: Medium

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.

Key Insights

  • Time points are represented in a circular manner, meaning after "23:59" it resets to "00:00".
  • The time difference can be calculated by converting the time strings into minutes since midnight.
  • Sorting the time points allows us to easily calculate the differences between consecutive times and also between the last and first time point (due to the circular nature).
  • The minimum difference can be found by comparing these calculated differences.

Space and Time Complexity

Time Complexity: O(n log n) - due to the sorting step.
Space Complexity: O(1) - if we ignore the space used by the input.

Solution

To solve this problem, we can use an array to store the minutes converted from the "HH:MM" format. The algorithm proceeds as follows:

  1. Convert each time point from "HH:MM" to the total minutes since midnight (i.e., HH * 60 + MM).
  2. Sort the array of minutes.
  3. Calculate the differences between each consecutive pair of times in the sorted array.
  4. Also calculate the difference between the last time and the first time (to account for the circular nature).
  5. Return the minimum difference found.

Code Solutions

def findMinDifference(timePoints):
    # Convert time points to minutes
    minutes = []
    for time in timePoints:
        hh, mm = map(int, time.split(':'))
        minutes.append(hh * 60 + mm)
    
    # Sort the minutes
    minutes.sort()

    # Initialize the minimum difference
    min_diff = float('inf')
    
    # Calculate differences between consecutive minutes
    for i in range(1, len(minutes)):
        min_diff = min(min_diff, minutes[i] - minutes[i - 1])
    
    # Check the difference between the first and last time point
    min_diff = min(min_diff, (minutes[0] + 1440) - minutes[-1])
    
    return min_diff
← Back to All Questions