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.
1function timeToMinutes(time) {
2 const [hours, minutes] = time.split(':').map(Number);
3 return hours * 60 + minutes;
4}
5
6function findMinDifference(timePoints) {
7 const minutes = timePoints.map(timeToMinutes);
8 minutes.sort((a, b) => a - b);
9
10 let minDiff = Infinity;
11 for (let i = 1; i < minutes.length; i++) {
12 minDiff = Math.min(minDiff, minutes[i] - minutes[i - 1]);
13 }
14
15 const wrapAroundDiff = minutes[0] + 1440 - minutes[minutes.length - 1];
16 minDiff = Math.min(minDiff, wrapAroundDiff);
17
18 return minDiff;
19}
20
21// Example usage:
22const timePoints = ["23:59", "00:00"];
23console.log(findMinDifference(timePoints));
In JavaScript, the approach is similar: convert times to minutes, sort, and find the smallest adjacent difference. Consider the time difference over 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.
1#include <vector>
#include <string>
#include <climits>
using namespace std;
int timeToMinutes(const string& time) {
int hours = stoi(time.substr(0, 2));
int minutes = stoi(time.substr(3, 2));
return hours * 60 + minutes;
}
int findMinDifference(vector<string>& timePoints) {
vector<bool> minutes(1440, false);
for (const auto& time : timePoints) {
int minute = timeToMinutes(time);
if (minutes[minute]) return 0;
minutes[minute] = true;
}
int first = -1, last = -1, prev = -1, minDiff = INT_MAX;
for (int i = 0; i < 1440; ++i) {
if (minutes[i]) {
if (first == -1) first = i;
if (prev != -1) minDiff = min(minDiff, i - prev);
prev = i;
last = i;
}
}
minDiff = min(minDiff, first + 1440 - last);
return minDiff;
}
int main() {
vector<string> timePoints = {"23:59", "00:00"};
cout << findMinDifference(timePoints) << endl;
return 0;
}
The C++ solution utilizes a boolean vector to monitor occupied minutes, efficiently calculating the smallest gap between true values, addressing the midnight lapse explicitly.