Minimum Time Difference

Published: Jan 20, 2023

Medium Math Sorting String

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”.

https://leetcode.com/problems/minimum-time-difference/

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)`