Watch 10 video solutions for Minimum Time Difference, a medium level problem involving Array, Math, String. This walkthrough by Nick White has 13,635 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Example 1:
Input: timePoints = ["23:59","00:00"] Output: 1
Example 2:
Input: timePoints = ["00:00","23:59","00:00"] Output: 0
Constraints:
2 <= timePoints.length <= 2 * 104timePoints[i] is in the format "HH:MM".Problem Overview: You receive a list of time points in HH:MM format. The task is to compute the smallest difference in minutes between any two time points. Because time wraps around midnight (e.g., 23:59 and 00:00), the comparison must also consider the circular nature of a 24‑hour clock.
Approach 1: Sorting and Finding Minimum Difference (O(n log n) time, O(n) space)
Convert each time string into total minutes from midnight (hour * 60 + minute). Store these values in an array and sort them. Once sorted, iterate through adjacent elements and compute the difference between each pair to track the minimum gap. The circular edge case is handled by comparing the last time of the day with the first time plus 1440 minutes. Sorting simplifies the comparison logic because the closest times must appear next to each other in the ordered list.
This method relies on basic operations from array processing and sorting. It works well for general input sizes and is easy to implement in most languages. Time complexity comes from sorting (O(n log n)), while the scan for differences runs in O(n). Space complexity is O(n) due to the converted minute array.
Approach 2: Using a Boolean Array to Track Minutes (O(n) time, O(1) space)
A day contains exactly 1440 minutes. Instead of sorting, allocate a boolean array of size 1440 and mark each minute that appears in the input. Convert every time string to its minute index and check if that index is already marked. If it is, the minimum difference is immediately 0 because duplicate times exist.
After marking all time points, scan the boolean array to locate consecutive marked minutes and compute their differences. Track the first and last seen minutes to correctly compute the circular difference across midnight. Because the array size is fixed (1440), the scan runs in constant time relative to the input size.
This technique uses ideas from array indexing and simple math transformations. The algorithm runs in O(n) time for inserting time points and O(1440) for scanning, which simplifies to O(n). Space complexity is effectively O(1) since the 1440‑length array is constant regardless of input size.
Recommended for interviews: The sorting approach is the most commonly expected solution because it is straightforward and demonstrates clean reasoning about ordering and edge cases like the midnight wrap‑around. Mentioning the boolean‑array optimization shows deeper insight: you recognize the bounded domain of minutes in a day and reduce the complexity to linear time. Showing both approaches signals strong problem‑solving depth in interviews.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Finding Minimum Difference | O(n log n) | O(n) | General solution that is simple to implement and commonly expected in interviews |
| Boolean Array for 1440 Minutes | O(n) | O(1) | When exploiting the fixed 24‑hour domain for a faster linear-time solution |