Minimum Time Difference
MedPrompt
Example 1:
Input: timePoints = ["23:59","00:00"]
Output: 1Example 2:
Input: timePoints = ["00:00","23:59","00:00"]
Output: 0
Constraints:
2 <= timePoints.length <= 2 * 104timePoints[i]is in the format "HH:MM".
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to compare every possible pair of time points in the list. For each pair, we calculate the time difference in minutes and keep track of the minimum difference found so far. A key detail is to handle the circular nature of the 24-hour clock; for example, the difference between "23:59" and "00:00" is 1 minute, not 1439 minutes.
Algorithm
- Initialize a variable
minDiffto a very large value (e.g.,Integer.MAX_VALUE). - Use nested loops to iterate through every unique pair of time points in the input list.
- For each pair of time strings, convert them into total minutes from midnight (00:00). For a time
HH:MM, the total minutes areHH * 60 + MM. - Calculate the absolute difference between the two minute values, let's call it
diff. - Since the clock is circular, the actual difference is the smaller of
diffand the wrap-around difference, which is(24 * 60) - diff. - Update
minDiffwith the minimum of its current value and the calculated circular difference. - After checking all pairs, return
minDiff.
Walkthrough
This method involves a nested loop structure. The outer loop picks a time point, and the inner loop iterates through the subsequent time points to form a pair. For each pair, we first need a helper function to convert the "HH:MM" string format into a numerical representation, such as the total number of minutes past midnight. Once we have two time points as minutes, say t1 and t2, we calculate two potential differences: the direct difference abs(t1 - t2) and the wrap-around difference (24 * 60) - abs(t1 - t2). The smaller of these two is the true minimum difference for that pair. We compare this value with a global minimum and update it if necessary. We repeat this for all pairs.
class Solution { public int findMinDifference(java.util.List<String> timePoints) { int minDiff = Integer.MAX_VALUE; int n = timePoints.size(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int time1 = convertToMinutes(timePoints.get(i)); int time2 = convertToMinutes(timePoints.get(j)); int diff = Math.abs(time1 - time2); // Consider the wrap-around difference int circularDiff = Math.min(diff, 24 * 60 - diff); minDiff = Math.min(minDiff, circularDiff); } } return minDiff; } private int convertToMinutes(String time) { String[] parts = time.split(":"); return Integer.parseInt(parts[0]) * 60 + Integer.parseInt(parts[1]); }}Complexity
Time
O(N^2), where N is the number of time points. We iterate through all possible pairs of time points, which is N * (N-1) / 2 pairs.
Space
O(1), as we only use a few variables to store the minimum difference and intermediate calculations, regardless of the input size.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space.
Cons
Highly inefficient, with a time complexity of O(N^2).
Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for larger inputs.
A more efficient approach involves sorting. If we convert all time points to minutes and sort them, the minimum difference must occur between two adjacent time points in the sorted list. We just need to iterate through the sorted list once to find the minimum difference between adjacent elements. We also must not forget to check the difference between the first and the last elements, which represents the wrap-around time difference on the clock.
Algorithm
- Create a new list to store the time points converted to minutes.
- Iterate through the input
timePointslist. For each time string, convert it to total minutes from midnight and add it to the new list. - Sort the list of minutes in ascending order.
- Initialize
minDiffto a very large value. - Iterate through the sorted list from the second element (
i = 1). Calculate the difference between the current element and the previous one (minutes[i] - minutes[i-1]) and updateminDiffif this difference is smaller. - After the loop, handle the wrap-around case. Calculate the difference between the first and last elements:
(minutes[0] + 24 * 60) - minutes[n-1]. - Update
minDiffone last time with this wrap-around difference. - Return
minDiff.
Walkthrough
First, we transform the list of time strings into a list of integers, where each integer is the total number of minutes from midnight. This takes O(N) time. Then, we sort this list of minutes, which takes O(N log N) time. After sorting, the time points are ordered chronologically. The smallest difference will be between consecutive elements. We can find this by iterating through the sorted list and calculating minutes.get(i) - minutes.get(i-1). The final step is to account for the circular clock. The difference between the last time and the first time of the day is also a candidate for the minimum. This is calculated as (first_time + 24*60) - last_time. The overall minimum is the minimum of all adjacent differences and this special wrap-around difference.
class Solution { public int findMinDifference(java.util.List<String> timePoints) { java.util.List<Integer> minutes = new java.util.ArrayList<>(); for (String time : timePoints) { minutes.add(convertToMinutes(time)); } java.util.Collections.sort(minutes); int minDiff = Integer.MAX_VALUE; for (int i = 1; i < minutes.size(); i++) { minDiff = Math.min(minDiff, minutes.get(i) - minutes.get(i - 1)); } // Handle the wrap-around case (difference between the last and first time) int wrapAroundDiff = (minutes.get(0) + 24 * 60) - minutes.get(minutes.size() - 1); minDiff = Math.min(minDiff, wrapAroundDiff); return minDiff; } private int convertToMinutes(String time) { String[] parts = time.split(":"); return Integer.parseInt(parts[0]) * 60 + Integer.parseInt(parts[1]); }}Complexity
Time
O(N log N), dominated by the sorting step. Converting times to minutes takes O(N) and finding the minimum difference after sorting takes another O(N).
Space
O(N), to store the list of time points after converting them to minutes. Some sorting algorithms might use additional space.
Trade-offs
Pros
Much faster than the brute-force approach for larger inputs.
The logic is still relatively straightforward.
Cons
Requires O(N) extra space to store the converted minutes.
The time complexity is dominated by sorting, which is not as fast as a linear-time solution.
The most optimal approach leverages the fact that there's a fixed, constant number of minutes in a day (1440). We can use a boolean array of size 1440 as a set of buckets, where each index represents a minute of the day. We mark the minutes that are present in the input list. If we encounter a time that's already been marked, the difference is 0. Otherwise, after marking all times, we can iterate through our bucket array to find the smallest gap between two marked minutes. This transforms the problem from comparing input points to scanning a fixed-size array.
Algorithm
- Note that there are
24 * 60 = 1440unique minutes in a day. If the input list has more than 1440 points, by the Pigeonhole Principle, at least two must be identical. In this case, the minimum difference is 0, so we can return immediately. - Create a boolean array
seenof size 1440, initialized tofalse. This array will act as a set of buckets for each minute of the day. - Iterate through the input
timePoints. For each time string: a. Convert it to total minutes,m. b. Checkseen[m]. If it'strue, we've found a duplicate time, so return 0. c. Otherwise, setseen[m]totrue. - After populating the
seenarray, iterate through it from minute 0 to 1439 to find the minimum gap betweentruevalues. - Use variables
firstandprevto keep track of the first and previously seen time (minute index). - When iterating, if
seen[i]istrue, update theminDiffwithi - prev(ifprevis valid). Then updateprevtoi. - After the loop, calculate the wrap-around difference between the first and last seen times:
(first + 1440) - prev. - Return the minimum of
minDiffand the wrap-around difference.
Walkthrough
This approach is a form of bucket sort. We create a boolean array of size 1440. First, we handle an edge case: if there are more than 1440 time points, at least two must be the same, so the minimum difference is 0. We then iterate through the input list, convert each time to minutes m, and mark the corresponding index m in our boolean array as true. If we try to mark an index that's already true, we've found a duplicate and can immediately return 0.
If we get through the whole input list without duplicates, we then scan our boolean array from index 0 to 1439. We use pointers first (to store the first minute we see) and prev (to store the previous minute we saw). As we find true values, we calculate the difference from the prev one and update our global minimum. Finally, we calculate the wrap-around difference between the first and last (prev will hold the last one) marked minutes and take the minimum. This gives us a linear time solution with constant space.
class Solution { public int findMinDifference(java.util.List<String> timePoints) { int totalMinutes = 24 * 60; if (timePoints.size() > totalMinutes) { return 0; // Pigeonhole principle } boolean[] seen = new boolean[totalMinutes]; for (String time : timePoints) { int minutes = Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(3)); if (seen[minutes]) { return 0; // Duplicate time found } seen[minutes] = true; } int minDiff = Integer.MAX_VALUE; int first = -1, prev = -1; for (int i = 0; i < totalMinutes; i++) { if (seen[i]) { if (first == -1) { first = i; } if (prev != -1) { minDiff = Math.min(minDiff, i - prev); } prev = i; } } // Handle wrap-around case int wrapAroundDiff = (first + totalMinutes) - prev; minDiff = Math.min(minDiff, wrapAroundDiff); return minDiff; }}Complexity
Time
O(N), where N is the number of time points. We iterate through the input list once (O(N)) and then iterate through the boolean array of constant size 1440 (O(1)). Thus, the total time complexity is dominated by the first pass.
Space
O(1), as the size of the boolean array is constant (1440) and does not depend on the size of the input list.
Trade-offs
Pros
Most efficient with O(N) time complexity.
Uses constant extra space, making it very memory-efficient.
Cons
The logic can be slightly more complex to implement correctly, especially handling the pointers for first, previous, and the wrap-around case.
Solutions
Solution
class Solution {public int findMinDifference(List<String> timePoints) { if (timePoints.size() > 24 * 60) { return 0; } List<Integer> mins = new ArrayList<>(); for (String t : timePoints) { String[] time = t.split(":"); mins.add(Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1])); } Collections.sort(mins); mins.add(mins.get(0) + 24 * 60); int res = 24 * 60; for (int i = 1; i < mins.size(); ++i) { res = Math.min(res, mins.get(i) - mins.get(i - 1)); } return res; }}class Solution {public: int findMinDifference(vector<string> &timePoints) { if (timePoints.size() > 24 * 60) return 0; vector<int> mins; for (auto t : timePoints) mins.push_back(stoi(t.substr(0, 2)) * 60 + stoi(t.substr(3))); sort(mins.begin(), mins.end()); mins.push_back(mins[0] + 24 * 60); int res = 24 * 60; for (int i = 1; i < mins.size(); ++i) res = min(res, mins[i] - mins[i - 1]); return res; }};''' >>> a = "000" >>> int(a) 0 >>> a = "00011" >>> int(a) 11 ''' class Solution : def findMinDifference ( self , timePoints : List [ str ]) -> int : if len ( timePoints ) > 24 * 60 : return 0 mins = sorted ( int ( t [: 2 ]) * 60 + int ( t [ 3 :]) for t in timePoints ) mins . append ( mins [ 0 ] + 24 * 60 ) # make it a circle, linking 1st and last slot return min ( abs ( a - b ) for a , b in pairwise ( mins )) # below also works, same logic # res = mins[-1] # for i in range(1, len(mins)): # res = min(res, mins[i] - mins[i - 1]) # return res ############ class Solution ( object ): def findMinDifference ( self , timePoints ): """ :type timePoints: List[str] :rtype: int """ ans = 24 * 60 times = [ 0 ] * len ( timePoints ) for i , time in enumerate ( timePoints ): h , m = map ( int , time . split ( ":" )) times [ i ] = h * 60 + m times . sort () for i in range ( len ( times ) - 1 ): ans = min ( ans , abs ( times [ i ] - times [ i + 1 ])) return min ( ans , 1440 - abs ( times [ 0 ] - times [ - 1 ]))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.