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.
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; }}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.