Minimum Time Difference
Medium · Math & Geometry · Explanation and code example
Minute Buckets on a Circular Day
How it works
Convert each time to a minute from zero to 1439. Mark seen minutes in a fixed-size table; a duplicate gives difference zero. Scan marked minutes in order and also compare the last with the first across midnight.
Steps
- Mark each minute and return zero for duplicates.
- Scan consecutive marked minutes for the smallest gap.
- Include 1440 - last + first.
Complexity
- Time: O(n + 1440).
- Space: O(1440).
Things to watch for
- The day wraps at midnight.
- Repeated time strings produce zero.
- A first/last comparison is needed even after ordered scanning.
Python code example
class Solution:
def findMinDifference(self, timePoints: list[str]) -> int:
seen = [False] * 1440
for time in timePoints:
minute = int(time[:2]) * 60 + int(time[3:])
if seen[minute]:
return 0
seen[minute] = True
first = previous = None
result = 1440
for minute, present in enumerate(seen):
if not present:
continue
if first is None:
first = minute
if previous is not None:
result = min(result, minute - previous)
previous = minute
return min(result, 1440 - previous + first)
C++ code example
class Solution {
public:
int findMinDifference(vector<string>& timePoints) {
int ans = 24 * 60;
int first = 24 * 60;
vector<bool> bucket(24 * 60);
for (const string& time : timePoints) {
const int num = stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3));
first = min(first, num);
if (bucket[num])
return 0;
bucket[num] = true;
}
int prev = first;
for (int i = first + 1; i < bucket.size(); ++i)
if (bucket[i]) {
ans = min(ans, i - prev);
prev = i;
}
return min(ans, 24 * 60 - prev + first);
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.