Sponsored
Convert the time into minutes from "00:00", sort, then find the smallest difference between any two adjacent times while also considering the difference across midnight.
Time Complexity: O(n log n) due to sorting where n is the number of time points. Space Complexity: O(n) since we store the times in minutes.
1def time_to_minutes(time):
2 hours, minutes = map(int, time.split(':'))
3 return hours * 60 + minutes
4
5def find_min_difference(time_points):
6 minutes = [time_to_minutes(time) for time in time_points]
7 minutes.sort()
8 min_diff = float('inf')
9 for i in range(1, len(minutes)):
10 min_diff = min(min_diff, minutes[i] - minutes[i - 1])
11 wrap_around_diff = minutes[0] + 1440 - minutes[-1]
12 min_diff = min(min_diff, wrap_around_diff)
13 return min_diff
14
15# Example usage
16time_points = ["23:59", "00:00"]
17print(find_min_difference(time_points))
This Python function converts each time point to minutes, sorts them, and determines the smallest difference between consecutive times. It also handles differences across midnight.
Mark each minute of the day in a boolean array once any time point corresponds to it. Then traverse the array to find the smallest gap between marked minutes, considering wrap-around. This is efficient because it eliminates the need for sorting.
Time Complexity: O(n + M), where M is 1440, the number of minutes in a day, n is the length of list.
Space Complexity: O(M), M = 1440, fixed.
1using System.Collections.Generic;
public class MinimumTimeDifference {
private static int TimeToMinutes(string time) {
int hours = int.Parse(time.Substring(0, 2));
int minutes = int.Parse(time.Substring(3, 2));
return hours * 60 + minutes;
}
public static int FindMinDifference(IList<string> timePoints) {
bool[] minutes = new bool[1440];
foreach (var time in timePoints) {
int minute = TimeToMinutes(time);
if (minutes[minute]) return 0;
minutes[minute] = true;
}
int first = -1, last = -1, prev = -1, minDiff = 1440;
for (int i = 0; i < 1440; ++i) {
if (minutes[i]) {
if (first == -1) first = i;
if (prev != -1) minDiff = Math.Min(minDiff, i - prev);
prev = i;
last = i;
}
}
minDiff = Math.Min(minDiff, first + 1440 - last);
return minDiff;
}
public static void Main() {
List<string> timePoints = new List<string> { "23:59", "00:00" };
Console.WriteLine(FindMinDifference(timePoints));
}
}
C# uses a boolean array to track each potential minute. The minimum gap between active minutes is calculated, including the wrap-around difference.