Jobs

Interviews

Discussions

Minimum Time Difference

Medium

Capital One

3 views

Topics:

ArraysStrings

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 1:

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

Example 2:

Input: timePoints = ["00:00","23:59","00:00"]
Output: 0

Constraints:

2 <= timePoints.length <= 2 * 10⁴
timePoints[i] is in the format "HH:MM".

Minimum Time Difference

Medium

Capital One

3 views

Topics:

ArraysStrings

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 1:

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

Example 2:

Input: timePoints = ["00:00","23:59","00:00"]
Output: 0

Constraints:

2 <= timePoints.length <= 2 * 10⁴
timePoints[i] is in the format "HH:MM".

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum number of time points in the input list?
Can the input list be empty or contain null/invalid time strings? If so, how should I handle those cases?
Are all time points guaranteed to be in the valid "HH:MM" format?
Are duplicate time points allowed in the input? If so, how should that affect the minimum difference calculation?
If the minimum time difference is zero, should I simply return 0, or is there a specific behavior expected (e.g., throw an error if duplicates exist when they shouldn't)?

Brute Force Solution

Approach

The brute force approach to finding the minimum time difference involves checking every possible pair of times. We will directly compare each time to every other time to find the smallest difference. This guarantees we find the correct answer, but might take a while if we have many times to compare.

Here's how the algorithm would work step-by-step:

Take the first time in the list.
Compare it to the second time and calculate the difference in minutes.
Compare the first time to the third time and calculate the difference in minutes.
Continue comparing the first time to all other times in the list, calculating the difference each time.
Keep track of the smallest difference you've found so far.
Now, take the second time in the list and repeat the process, comparing it to all the *other* times (except itself).
Again, update the smallest difference if you find a smaller one.
Repeat this process for every time in the list, comparing each time to all the other times.
After comparing all possible pairs, the smallest difference you kept track of is your answer.

Code Implementation

def minimum_time_difference_brute_force(time_points):
    minimum_difference = float('inf')

    for i in range(len(time_points)):
        for j in range(len(time_points)):
            if i != j:
                # Prevent comparison of the same time with itself

                time_difference = calculate_time_difference(time_points[i], time_points[j])

                # Need to compare to both the standard and reverse time difference

                minimum_difference = min(minimum_difference, time_difference)

    return minimum_difference

def calculate_time_difference(time1, time2):
    hour1, minute1 = map(int, time1.split(':'))
    hour2, minute2 = map(int, time2.split(':'))

    total_minutes1 = hour1 * 60 + minute1
    total_minutes2 = hour2 * 60 + minute2

    difference = abs(total_minutes1 - total_minutes2)

    # Need to take the min of the direct difference and the inverse difference

    return min(difference, 1440 - difference)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n time points in the input list. For each time point, it compares it to every other time point in the list. This results in a nested loop structure where for each of the n time points, we perform approximately n comparisons. Therefore the total number of comparisons is proportional to n multiplied by n, resulting in O(n²) time complexity.

Space Complexity

O(1) – The brute force approach only utilizes a variable to store the minimum difference found so far, and potentially loop indices. The amount of extra memory used does not scale with the number of times in the input list. Therefore, the space complexity is constant, or O(1).

Optimal Solution

Approach

The goal is to find the smallest time difference between any two times in a given list. The core idea is to convert all times into a standard unit (like minutes) and then find the smallest difference between adjacent times after sorting them.

Here's how the algorithm would work step-by-step:

First, transform each time in the list into its equivalent number of minutes from midnight.
Next, sort these minute values in ascending order.
After sorting, compute the difference between each pair of consecutive times.
Also, compute the difference between the last time and the first time (considering the times wrap around within a 24-hour clock).
Finally, find the smallest of all these differences.

Code Implementation

def find_min_difference(time_points):
    minutes = []
    for time in time_points:
        hour, minute = map(int, time.split(':'))
        total_minutes = hour * 60 + minute
        minutes.append(total_minutes)

    minutes.sort()

    min_difference = float('inf')

    # Iterate and compute the diff between adjacent times
    for i in range(len(minutes) - 1):
        difference = minutes[i + 1] - minutes[i]
        min_difference = min(min_difference, difference)

    # Account for the wrap-around case
    wrap_around_difference = minutes[0] + 1440 - minutes[-1]
    min_difference = min(min_difference, wrap_around_difference)

    return min_difference

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm first iterates through the input list of times (size n) to convert each time string into minutes. This conversion step takes O(n) time. Next, the algorithm sorts the list of minutes, which typically uses an efficient sorting algorithm like merge sort or quicksort, giving it a time complexity of O(n log n). After sorting, the algorithm iterates through the sorted list to calculate differences between adjacent times, which takes O(n) time. Finally, finding the minimum difference takes O(n) time as well. The dominant operation is the sorting step, so the overall time complexity is O(n log n).

Space Complexity

O(N) – The space complexity is dominated by the creation of a new list to store the converted times in minutes. This list will have the same number of elements as the input list of times, denoted as N. Sorting this list, depending on the algorithm used, could also require auxiliary space. Therefore, the auxiliary space is directly proportional to the input size N, giving us a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input list.	Return 0, as no difference can be calculated.
Input list with only one time point.	Return 0, since no comparison can be made with another time point.
Input list with all identical time points.	The minimum difference will be 0; the algorithm should correctly return this result.
Input list with time points very close to 00:00 and 23:59 (wrap-around case).	Ensure that the minimum difference calculation correctly considers the circular nature of the clock, checking both direct difference and wrap-around difference.
Large input list (scalability).	Sort the time points and calculate the differences between adjacent time points to ensure the algorithm scales reasonably.
Time points not in valid 'HH:MM' format.	Validate that the input strings conform to the expected 'HH:MM' format; return an error or ignore the invalid time point.
Time points with invalid hour or minute values (e.g., 24:00 or 12:60).	Validate that the hour and minute values are within the valid range (0-23 for hours, 0-59 for minutes); return an error or ignore the invalid time point.
Integer overflow when calculating the difference in minutes.	Use appropriate data types (e.g., long) to store the minute differences to prevent potential integer overflow issues.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum number of time points in the input list?
Can the input list be empty or contain null/invalid time strings? If so, how should I handle those cases?
Are all time points guaranteed to be in the valid "HH:MM" format?
Are duplicate time points allowed in the input? If so, how should that affect the minimum difference calculation?
If the minimum time difference is zero, should I simply return 0, or is there a specific behavior expected (e.g., throw an error if duplicates exist when they shouldn't)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first time in the list.
Compare it to the second time and calculate the difference in minutes.
Compare the first time to the third time and calculate the difference in minutes.
Continue comparing the first time to all other times in the list, calculating the difference each time.
Keep track of the smallest difference you've found so far.
Now, take the second time in the list and repeat the process, comparing it to all the *other* times (except itself).
Again, update the smallest difference if you find a smaller one.
Repeat this process for every time in the list, comparing each time to all the other times.
After comparing all possible pairs, the smallest difference you kept track of is your answer.

Code Implementation

def minimum_time_difference_brute_force(time_points):
    minimum_difference = float('inf')

    for i in range(len(time_points)):
        for j in range(len(time_points)):
            if i != j:
                # Prevent comparison of the same time with itself

                time_difference = calculate_time_difference(time_points[i], time_points[j])

                # Need to compare to both the standard and reverse time difference

                minimum_difference = min(minimum_difference, time_difference)

    return minimum_difference

def calculate_time_difference(time1, time2):
    hour1, minute1 = map(int, time1.split(':'))
    hour2, minute2 = map(int, time2.split(':'))

    total_minutes1 = hour1 * 60 + minute1
    total_minutes2 = hour2 * 60 + minute2

    difference = abs(total_minutes1 - total_minutes2)

    # Need to take the min of the direct difference and the inverse difference

    return min(difference, 1440 - difference)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, transform each time in the list into its equivalent number of minutes from midnight.
Next, sort these minute values in ascending order.
After sorting, compute the difference between each pair of consecutive times.
Also, compute the difference between the last time and the first time (considering the times wrap around within a 24-hour clock).
Finally, find the smallest of all these differences.

Code Implementation

def find_min_difference(time_points):
    minutes = []
    for time in time_points:
        hour, minute = map(int, time.split(':'))
        total_minutes = hour * 60 + minute
        minutes.append(total_minutes)

    minutes.sort()

    min_difference = float('inf')

    # Iterate and compute the diff between adjacent times
    for i in range(len(minutes) - 1):
        difference = minutes[i + 1] - minutes[i]
        min_difference = min(min_difference, difference)

    # Account for the wrap-around case
    wrap_around_difference = minutes[0] + 1440 - minutes[-1]
    min_difference = min(min_difference, wrap_around_difference)

    return min_difference

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input list.	Return 0, as no difference can be calculated.
Input list with only one time point.	Return 0, since no comparison can be made with another time point.
Input list with all identical time points.	The minimum difference will be 0; the algorithm should correctly return this result.
Input list with time points very close to 00:00 and 23:59 (wrap-around case).	Ensure that the minimum difference calculation correctly considers the circular nature of the clock, checking both direct difference and wrap-around difference.
Large input list (scalability).	Sort the time points and calculate the differences between adjacent time points to ensure the algorithm scales reasonably.
Time points not in valid 'HH:MM' format.	Validate that the input strings conform to the expected 'HH:MM' format; return an error or ignore the invalid time point.
Time points with invalid hour or minute values (e.g., 24:00 or 12:60).	Validate that the hour and minute values are within the valid range (0-23 for hours, 0-59 for minutes); return an error or ignore the invalid time point.
Integer overflow when calculating the difference in minutes.	Use appropriate data types (e.g., long) to store the minute differences to prevent potential integer overflow issues.