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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Time Difference

Number: 539

Difficulty: Medium

Paid? No

Companies: Meta, Google, Amazon, Palantir Technologies, Microsoft, Bloomberg, Zoho

Problem Description

Given a list of 24-hour clock time points in "HH:MM" format, the task is to determine the minimum difference in minutes between any two time points in the list.

Key Insights

  • Convert each time point to minutes since midnight for easier computation.
  • Sort the converted time points to quickly compare adjacent times.
  • Compute the difference between adjacent sorted time points.
  • Account for the circular nature of the clock by comparing the last and first time points (considering the day wrap-around).
  • If any duplicate times exist, the minimum difference is immediately 0.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) for storing the converted time points.

Solution

The solution involves converting each "HH:MM" string into an integer representing the minutes elapsed since midnight. Once this is done for all time points, sort the list to evaluate consecutive differences efficiently. After computing the differences between each adjacent pair, also compute the difference between the last and first time point by considering the wrap-around (i.e., add 1440 minutes for a complete day and subtract the difference). The smallest of these differences is the answer. This approach leverages sorting to reduce the problem to a linear scan afterwards.

Code Solutions

# Python solution for Minimum Time Difference

def findMinDifference(timePoints):
    # Helper function to convert "HH:MM" to total minutes
    def time_to_minutes(t):
        hours, minutes = map(int, t.split(":"))
        return hours * 60 + minutes

    # Convert each time point to minutes
    minutes_list = [time_to_minutes(time) for time in timePoints]
    
    # Sort the time points
    minutes_list.sort()

    # Initialize min_diff with the maximum possible value (i.e., one day)
    min_diff = 1440

    # Iterate through sorted list to compute differences between consecutive times
    for i in range(1, len(minutes_list)):
        min_diff = min(min_diff, minutes_list[i] - minutes_list[i - 1])
    
    # Don't forget the circular difference between the last and first time point
    circular_diff = (1440 - minutes_list[-1]) + minutes_list[0]
    min_diff = min(min_diff, circular_diff)
    
    return min_diff

# Example usage:
# print(findMinDifference(["23:59", "00:00"]))  # Output: 1
← Back to All Questions