NeetCode #926LC-539MediumMath & Geometry
← Back to All Problems#926 · #539 · Minimum Time Difference(最小时间差)
📌 Problem Statement & Constraints
Given a list
timePoints of clock times formatted HH:MM on a 24-hour clock, return the smallest difference in minutes between any two of them. The day wraps around, so 23:59 and 00:00 are one minute apart. Constraints: 2 <= timePoints.length <= 2 * 10^4.💡 Core Algorithmic Approaches
- Convert each timestamp to minutes since
00:00usingint(t[:2]) * 60 + int(t[3:]). - After sorting, the minimum gap must be between two adjacent times: a non-adjacent pair is always at least as large as some adjacent gap contained inside it.
- Handle the wrap-around separately: the gap between the last and first entries across midnight is
1440 + first - last. - Return the minimum over the adjacent gaps and the wrap-around gap.
💻 Benchmark Python3 Implementation
class Solution:
def findMinDifference(self, timePoints: List[str]) -> int:
mins = sorted(int(t[:2]) * 60 + int(t[3:]) for t in timePoints)
res = 1440 + mins[0] - mins[-1] # wrap around midnight
for i in range(1, len(mins)):
res = min(res, mins[i] - mins[i - 1])
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): the sort dominates.
💾 Space Complexity
O(n): the array of minute values.
⚠️ Interview Pitfalls & Follow-ups
- Ignoring the wrap-around gap: for the pair
23:59and00:00the answer is 1, not 1439. - Comparing the strings directly: lexicographic order does not match chronological order, e.g.
9:00sorts after10:00as text. - Parsing the colon position wrongly: the hours are
t[:2]and the minutes aret[3:], because index 2 is the colon. - Assuming the minimum gap can be between non-adjacent entries: after sorting, the global minimum is always one of the adjacent gaps.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.