Dare2Solve
The problem requires determining the minimum difference in time between any two given time points, considering that time wraps around after midnight (i.e., 24-hour format). Time points are provided in "HH:MM" format, and we need to return the smallest difference between any two time points in minutes.
The key observation is that the time points are circular, meaning that we should account for the fact that the time difference between the last and first time points might be the smallest. Converting the time points into minutes from midnight allows for easier comparison of time differences. Sorting the time points in minutes and calculating consecutive differences helps us find the minimum difference efficiently.
O(n log n), where n is the number of time points. Sorting the time points takes O(n log n), and calculating the differences takes O(n).
O(n), as we store the time points in minutes in an additional list.
class Solution {
public:
int findMinDifference(std::vector<std::string>& timePoints) {
std::vector<int> minutes;
// Convert time strings into minutes
for (std::string& time : timePoints) {
int hours = std::stoi(time.substr(0, 2));
int mins = std::stoi(time.substr(3, 2));
minutes.push_back(hours * 60 + mins);
}
// Sort the time in minutes
std::sort(minutes.begin(), minutes.end());
// Append the first time + 1440 to handle the circular case
minutes.push_back(minutes[0] + 1440);
// Find the minimum difference
int minDiff = INT_MAX;
for (int i = 1; i < minutes.size(); ++i) {
minDiff = std::min(minDiff, minutes[i] - minutes[i - 1]);
}
return minDiff;
}
};
class Solution:
def findMinDifference(self, timePoints: List[str]) -> int:
# Convert time strings into minutes
minutes = []
for time in timePoints:
hours, mins = map(int, time.split(":"))
minutes.append(hours * 60 + mins)
# Sort the time in minutes
minutes.sort()
# Append the first time + 1440 to handle the circular case
minutes.append(minutes[0] + 1440)
# Find the minimum difference
minDiff = float('inf')
for i in range(1, len(minutes)):
minDiff = min(minDiff, minutes[i] - minutes[i - 1])
return minDiff
class Solution {
public int findMinDifference(List<String> timePoints) {
List<Integer> minutes = new ArrayList<>();
// Convert time strings into minutes
for (String time : timePoints) {
String[] split = time.split(":");
int hours = Integer.parseInt(split[0]);
int mins = Integer.parseInt(split[1]);
minutes.add(hours * 60 + mins);
}
// Sort the time in minutes
Collections.sort(minutes);
// Append the first time + 1440 to handle the circular case
minutes.add(minutes.get(0) + 1440);
// Find the minimum difference
int minDiff = Integer.MAX_VALUE;
for (int i = 1; i < minutes.size(); i++) {
minDiff = Math.min(minDiff, minutes.get(i) - minutes.get(i - 1));
}
return minDiff;
}
}
var findMinDifference = function (timePoints) {
timePoints.sort();
timePoints = timePoints.map(el => {
let [hours, minutes] = el.split(':');
return Number(hours) * 60 + Number(minutes);
})
timePoints.push(timePoints[0] + 1440);
let minDiff = Infinity;
for (let i = 1; i < timePoints.length; i++) {
minDiff = Math.min(minDiff, timePoints[i] - timePoints[i - 1]);
}
return minDiff;
};