539. Minimum Time Difference
Problem Description
The task is to find the smallest difference in minutes between any pair of given time points where time points are represented in "HH:MM" (24-hour) format. The expectation is to calculate and return the minimum number of minutes that one would need to add or subtract to convert one time into another, considering all possible pairs within the list.
Intuition
To arrive at the intuitive solution, consider that time points are cyclical; 00:00 comes after 23:59 in a day. Hence, the times form a circular sequence. If we have the times as minutes past midnight, then the smallest difference is not necessarily between consecutive times in a 24-hour window but may span across midnight. Here's the step-by-step intuition:
-
Convert to minutes: Since we are to find differences in minutes, and times are given in hours and minutes, we convert everything into minutes to simplify calculations.
-
Sort the times: Sorting makes consecutive time points the nearest neighbors, saving us from checking each pair of time points. After sorting, the time points form a timeline from the earliest to the latest within a day.
-
Deal with the 24-hour wraparound: A crucial step is to handle the end-of-day wraparound when the difference between a late time and an early time spans over midnight (e.g. comparing 23:50 and 00:05). To manage this, we clone the first time point, add 24 hours (in minutes) to it, and append it to the sorted times; this simplifies our loop. The minimum difference can still be found in consecutive times because of our circular timeline.
-
Find the minimum difference: Loop through the sorted minutes and find the minimum difference between each adjacent pair, including the end-of-day wraparound we created.
This approach ensures that all comparisons needed to ascertain the minimum time difference are made, with the cyclical nature of time taken into account, using a single loop through the points.
Solution Approach
The solution provided here leverages a few straightforward concepts: sorting, modular arithmetic (to handle the circular nature of time), and greedy algorithms (to find the minimum value). The detailed solution approach is as follows:
-
Upper Bound Check: Before we begin any processing, we check if the list has more than
24 * 60
time points. If it does, it means there must be a duplicate time since there are only24 * 60
minutes in a day. In this case, the minimum difference between any two time-points would be0
, as two or more time points are the same. -
Convert Times to Minutes: We convert each time-point from the
HH:MM
format to minutes since midnight using a list comprehension. This involves splitting each time string into hours and minutes, converting them to integers, and then to total minutes:int(t[:2]) * 60 + int(t[3:])
. -
Sort Minutes: Sorting the minute values helps to place the time points on a timeline from the smallest to the largest, making it easier to calculate consecutive differences.
-
Handle Circular Case: To address the wraparound at the end of the day (i.e., 00:00 is technically
0
minutes since midnight but follows 23:59 from the previous day), we append the smallest time (plus one full day,24 * 60
minutes) to the end of our list. -
Initialize Result: We set a variable
res
with a high initial value (using the last element which we artificially inflated in the previous step). -
Find Minimum Difference: Loop through the list starting from index
1
, and calculate the difference between the current element and the previous element (mins[i] - mins[i - 1]
). If the difference is smaller than the currentres
, updateres
. The process ensures we find the smallest difference.
By looping through only once and having our times sorted, we effectively use a greedy approach to find the minimum time difference without having to compare every single pair, which would be less efficient.
The Solution
class provided represents an implementation of these steps, using Python's list and sorting capabilities to obtain the result efficiently.
1class Solution:
2 def findMinDifference(self, timePoints: List[str]) -> int:
3 if len(timePoints) > 24 * 60:
4 return 0
5 mins = sorted(int(t[:2]) * 60 + int(t[3:]) for t in timePoints)
6 mins.append(mins[0] + 24 * 60)
7 res = mins[-1]
8 for i in range(1, len(mins)):
9 res = min(res, mins[i] - mins[i - 1])
10 return res
In summary, the algorithm uses an upper bound check, conversion to a single unit (minutes), sorting, circular case handling, and greedy minimum difference calculation to solve the problem effectively.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose we have the following list of time points:
1["23:59", "00:00", "12:34", "22:00"]
Now, let's walk through the steps:
-
Upper Bound Check: The list has fewer than
24 * 60
time points, so we need to proceed with the rest of the calculation since there is no immediate indication of duplicate times. -
Convert Times to Minutes: We convert each time point to the number of minutes since midnight.
- "23:59" becomes
23 * 60 + 59 = 1439
minutes. - "00:00" becomes
0 * 60 + 0 = 0
minutes. - "12:34" becomes
12 * 60 + 34 = 754
minutes. - "22:00" becomes
22 * 60 + 0 = 1320
minutes.
- "23:59" becomes
-
Sort Minutes: We sort the minute values to get
[0, 754, 1320, 1439]
. -
Handle Circular Case: We append the smallest time (plus one full day) to the end. So,
0 + 24 * 60 = 1440
minutes is added to the list, resulting in[0, 754, 1320, 1439, 1440]
. -
Initialize Result: We set
res
to a high initial value using the last element which was inflated in the previous step, sores = 1440
. -
Find Minimum Difference: We calculate the differences between consecutive elements.
- Difference between
754
and0
is754 - 0 = 754
. - Difference between
1320
and754
is1320 - 754 = 566
. - Difference between
1439
and1320
is1439 - 1320 = 119
. - Difference between
1440
and1439
is1440 - 1439 = 1
.
- Difference between
The smallest difference is 1
, so we update res
to 1
.
Following these steps, the solution class's method findMinDifference
would return 1
as the smallest difference in minutes between any two given time points in this list.
Solution Implementation
1class Solution:
2 def findMinDifference(self, time_points: List[str]) -> int:
3 # If there are more time points than the total minutes in a day,
4 # it means at least two time_points are the same,
5 # hence the minimum difference is 0.
6 if len(time_points) > 24 * 60:
7 return 0
8
9 # Convert the time points to minutes and sort them.
10 minutes = sorted(int(time[:2]) * 60 + int(time[3:]) for time in time_points)
11
12 # Add the first element plus 24 hours to the end of the list
13 # to calculate the circular difference.
14 minutes.append(minutes[0] + 24 * 60)
15
16 # Initialize the result with a maximum value for later comparison.
17 min_difference = minutes[-1]
18
19 # Calculate the minimum difference by iterating through the sorted minutes.
20 for i in range(1, len(minutes)):
21 min_difference = min(min_difference, minutes[i] - minutes[i - 1])
22
23 # Return the minimum difference found.
24 return min_difference
25
1class Solution {
2
3 public int findMinDifference(List<String> timePoints) {
4 // If there are more time points than minutes in a day, we have at least two identical times.
5 if (timePoints.size() > 24 * 60) {
6 return 0;
7 }
8
9 // Convert the list of time points into minutes since midnight.
10 List<Integer> timePointsInMinutes = new ArrayList<>();
11 for (String timePoint : timePoints) {
12 String[] time = timePoint.split(":");
13 int minutes = Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]);
14 timePointsInMinutes.add(minutes);
15 }
16
17 // Sort the list of time points in minutes.
18 Collections.sort(timePointsInMinutes);
19
20 // Add the first time point again to the end of the list converted to the next day,
21 // to make it easier to calculate the min difference with the last time point.
22 timePointsInMinutes.add(timePointsInMinutes.get(0) + 24 * 60);
23
24 // Initialize the minimum difference to the maximum possible value (24 hours),
25 // which will be updated in the following loop.
26 int minDifference = 24 * 60;
27 for (int i = 1; i < timePointsInMinutes.size(); ++i) {
28 // Update the minimum difference if a smaller difference is found.
29 minDifference = Math.min(minDifference, timePointsInMinutes.get(i) - timePointsInMinutes.get(i - 1));
30 }
31
32 // Return the minimum difference in minutes between any two time points.
33 return minDifference;
34 }
35}
36
1class Solution {
2public:
3 int findMinDifference(vector<string>& timePoints) {
4 // If there are more time points than minutes in a day, there must be a duplicate.
5 // Since duplicate times would have 0 difference, return 0.
6 const int totalMinutesInDay = 24 * 60;
7 if (timePoints.size() > totalMinutesInDay) {
8 return 0;
9 }
10
11 // Vector to hold the time points in minutes since midnight.
12 vector<int> minutes;
13
14 // Convert time points from string to minutes since midnight.
15 for (const auto& time : timePoints) {
16 int hour = stoi(time.substr(0, 2));
17 int minute = stoi(time.substr(3));
18 minutes.push_back(hour * 60 + minute);
19 }
20
21 // Sort the converted time points.
22 sort(minutes.begin(), minutes.end());
23
24 // Append the first time point plus 24 hours to handle the circular time comparison.
25 minutes.push_back(minutes[0] + totalMinutesInDay);
26
27 // Initialize the result with the maximum possible difference.
28 int minDifference = totalMinutesInDay;
29
30 // Loop through the sorted time points to find the minimum difference.
31 for (int i = 1; i < minutes.size(); ++i) {
32 // Compare each pair of adjacent time points.
33 minDifference = min(minDifference, minutes[i] - minutes[i - 1]);
34 }
35
36 // Return the minimum time difference found.
37 return minDifference;
38 }
39};
40
1function findMinDifference(timePoints: string[]): number {
2 // Convert each time point to minutes since the start of the day and sort the array
3 const minutesArray = timePoints
4 .map(time => {
5 const hours = Number(time.slice(0, 2));
6 const minutes = Number(time.slice(3, 5));
7 return hours * 60 + minutes;
8 })
9 .sort((a, b) => a - b);
10
11 const numTimePoints = minutesArray.length;
12 let minimumDifference = Infinity;
13
14 // Find the minimum difference between consecutive time points
15 for (let i = 0; i < numTimePoints - 1; i++) {
16 minimumDifference = Math.min(minimumDifference, minutesArray[i + 1] - minutesArray[i]);
17 }
18
19 // To account for the circular nature of the clock,
20 // calculate the difference between the last and first time point across midnight
21 const differenceAcrossMidnight = minutesArray[0] + 24 * 60 - minutesArray[numTimePoints - 1];
22 minimumDifference = Math.min(minimumDifference, differenceAcrossMidnight);
23
24 return minimumDifference;
25}
26
Time and Space Complexity
Time Complexity
The given code comprises of several operations. Let's analyze them step-by-step:
- Checking Length of
timePoints
: The operationlen(timePoints)
takesO(n)
time, wheren
is the number of elements intimePoints
. - Conversion and Sorting of
timePoints
: The conversion takes linear time,O(n)
as each element is processed once. Sorting the converted times will takeO(n log n)
time wheren
is the length of thetimePoints
. - Appending an Element: Takes
O(1)
time. - Iterating over the Sorted
mins
List: This loop runs inO(n)
time.
The dominant term here is O(n log n)
due to the sorting step. Thus the overall time complexity is O(n log n)
.
Space Complexity
The space complexity includes the space required for the inputs and any additional space used by the algorithm to compute the final result:
- List
mins
: Additional space is required to store the converted time points, which isO(n)
. - Constant Space: Used by variables for calculating the minimum, such as
res
and the loop indexi
.
Hence, the space complexity of the code is O(n)
where n
is the number of elements in timePoints
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.