Published: Jan 20, 2023
Problem Description
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.
Constraints:
2 <= timePoints.length <= 2 * 10**4
timePoints[i]
is in the format “HH:MM”.
Examples
Example 1
Input: timePoints = ["23:59","00:00"]
Output: 1
Example 2
Input: timePoints = ["00:00","23:59","00:00"]
Output: 0
How to Solve
A couple of key points are:
- convert time in string to minutes
- handle minimum + 1 day and maximum time
Other than that, nothing is special. Sort the minutes array and compare time difference to next time. The problem asks the minimum time difference, so a comparison of two adjacent values is enough after sorting. The tricky part is a time might be next day’s time. To handle this, the solution here added a time which is the minimum + 24 * 60 minutes. When the loop is over, the minimum difference is there.
Solution
class MinimumTimeDifference {
public:
int findMinDifference(vector<string>& timePoints) {
auto timeToMins = [](const string &t) {
return stoi(t.substr(0, 2)) * 60 + stoi(t.substr(3, 2));
};
vector<int> points;
for (auto &t : timePoints) {
points.push_back(timeToMins(t));
}
sort(points.begin(), points.end());
points.push_back(points[0] + 24 * 60);
int min_diff = 24 * 60 + 1;
for (int i = 1; i < points.size(); ++i) {
min_diff = min(min_diff, points[i] - points[i - 1]);
}
return min_diff;
}
};
class MinimumTimeDifference:
def findMinDifference(self, timePoints: List[str]) -> int:
def timeToMins(t):
return int(t[0:2]) * 60 + int(t[3:5])
points = sorted([timeToMins(t) for t in timePoints])
points.append(points[0] + 24 * 60)
min_diff = float('inf')
for i in range(1, len(points)):
min_diff = min(min_diff, points[i] - points[i - 1])
return min_diff
Complexities
- Time:
O(n * log(n))
- Space:
O(n)