539. Minimum Time Difference
Model: qwen3.5:9b
Topics: String
FAANG asked: 0
Acceptance rate: 52.4%
Problem Breakdown
We are given a list of times in “HH:MM” format representing points on a 24-hour clock. The goal is to find the minimum difference in minutes between any two time-points within that list.
Key inputs and outputs include:
- Input: A list of strings (
timePoints), where each string follows strict “HH:MM” formatting (00-23 for hours, 00-59 for minutes). The length is guaranteed to be at least 2 based on constraints. - Output: An integer representing the smallest positive difference in minutes between any pair of times.
Implicit edge cases and tricky aspects:
- Circular Nature: Time wraps around midnight (e.g., “00:00” follows “23:59”). A naive linear subtraction fails here without special handling for the boundary crossing.
- Duplicates: If two time-points are identical, the difference is 0. This must be captured correctly.
- Scale: With up to elements, an solution will exceed typical execution limits (Time Limit Exceeded). We need a more efficient approach than comparing every pair.
Intuition
A brute-force strategy would involve iterating through all pairs of time-points and calculating the absolute difference for each. This results in complexity, which is too slow given can be up to 20,000 ( operations).
To optimize, we should observe that if times are ordered linearly (sorted), the minimum difference between any two elements must occur between adjacent neighbors in that sorted sequence. If you have three points , then , so checking non-adjacent pairs is redundant for finding the minimum gap within a linear segment.
However, because time is circular (24-hour cycle), we must also consider the “wrap-around” distance between the last element and the first element in our sorted list. The key insight is:
- Convert all times to minutes from midnight (0-1439) for easy arithmetic.
- Sort these integers.
- Iterate through adjacent pairs to find local minimums.
- Explicitly check the circular gap between
lastandfirst.
Approach
The algorithm proceeds in three main steps:
- Normalization: Parse each “HH:MM” string into an integer representing minutes from midnight (). This allows direct numerical comparison.
- Sorting & Linear Scan: Sort the list of minute values. Iterate through the sorted array, calculating
current - previousfor every adjacent pair and updating a running minimum (min_diff). Initializemin_diffto infinity or handle duplicates (where diff is 0). - Circular Check: Calculate the difference between the first element plus one full day ( minutes) and the last element:
(first + 24*60) - last. Compare this against our running minimum.
This approach ensures we cover all adjacent gaps in a linear timeline as well as the wrap-around gap, guaranteeing correctness with complexity due to sorting.
Complexity Analysis
- Time Complexity: . The dominant operation is sorting the list of time integers ( elements). Converting strings takes per element (fixed format), and iterating through the sorted array takes . Total: .
- Space Complexity: . We store an integer list of size for sorting. If we modify input in-place (not recommended here), it could be auxiliary, but standard Python sort creates a new structure or uses internal buffers proportional to .
Solution
def findMinDifference(timePoints):
# Convert "HH:MM" strings to minutes from midnight for easier comparison.
times = []
for t in timePoints:
h, m = map(int, t.split(':'))
times.append(h * 60 + m)
# Sort the minute values to easily find adjacent differences.
times.sort()
min_diff = float('inf')
# Check linear gaps between adjacent elements in sorted list.
for i in range(len(times) - 1):
diff = times[i+1] - times[i]
if diff < min_diff:
min_diff = diff
# Handle the circular wrap-around case (last element to first).
# Add 24*60 minutes to the first element to simulate next day.
circular_gap = (times[0] + 1440) - times[-1]
if circular_gap < min_diff:
min_diff = circular_gap
return min_diff
Edge Cases Handled
- Duplicate Times: If the list contains
["08:00", "08:00"], sorting places them adjacent. The difference is 0, which correctly updatesmin_diff. - Midnight Wrap-Around: For inputs like
["23:59", "00:00"], the linear scan sees a large gap (1439 minutes). The explicit circular check calculates(0 + 1440) - 1439 = 1minute, correctly identifying this as the minimum. - Single Element: While constraints specify , if only one time existed,
min_diffwould remain infinity (or require specific handling). The current logic assumes valid input per constraints but handles duplicates naturally via sorting.