Leetcode 539. Minimum Time Difference
Problem Description
You are given a list of string time points that represents time in "Hour:Minutes" format in 24-hours clock. Your task is to find the minimum difference in minutes between any two time points in the list.
For example, consider the list ["23:59", "00:00"]. The difference between "23:59" and "00:00" is 1 minute. Therefore, the output should be 1.
Note that the number of time points in the given list is at least 2 and won't exceed 20000. The input time is valid and ranges from 00:00 to 23:59.
Approach
The solution uses a bucket sort approach to solve this problem. Here is how it works:
-
It first initializes a bucket array of size 1440 (24*60) to represent all minutes in a day. It also initializes variable
ans
to 1440 andfirst
to 1440. -
Then for each time point in the list, it converts the time point into minutes from midnight and updates
first
if it is smaller than the previousfirst
. It also marks the corresponding position in the bucket as true. -
If the time point already exists in the bucket, it returns 0 as this implies two time points are the same and the difference is naturally 0.
-
Then it goes through the bucket again from
first + 1
to the end. If it finds a true value, it means there is a time point at that minute. It updatesans
to the smaller value between the currentans
and the difference between the current minute andprev
.prev
is then updated to be the current minute. -
Finally, it also checks the circular condition, which is the difference between the first time point in the day and the last time point in the previous day. It updates
ans
to the smaller value between the currentans
and24 * 60 - prev + first
.
Python Solution
1 2python 3class Solution: 4 def findMinDifference(self, timePoints): 5 bucket = [False] * 1440 # 24*60 minutes in a day 6 first = prev = 1440 7 ans = 1440 8 9 for time in timePoints: 10 hour, minute = map(int, time.split(":")) 11 num = hour * 60 + minute 12 first = min(first, num) 13 if bucket[num]: 14 return 0 15 bucket[num] = True 16 17 for i in range(first + 1, 1440): 18 if bucket[i]: 19 ans = min(ans, i - prev) 20 prev = i 21 22 return min(ans, 1440 - prev + first)
Java Solution
1 2java 3import java.util.*; 4 5public class Solution { 6 public int findMinDifference(List<String> timePoints) { 7 boolean[] bucket = new boolean[1440]; 8 int first = 1440; 9 int prev = 1440; 10 int ans = 1440; 11 12 for (String time : timePoints) { 13 int hour = Integer.parseInt(time.substring(0, 2)); 14 int minute = Integer.parseInt(time.substring(3)); 15 int num = hour * 60 + minute; 16 first = Math.min(first, num); 17 if (bucket[num]) { 18 return 0; 19 } 20 bucket[num] = true; 21 } 22 23 for (int i = first + 1; i < 1440; i++) { 24 if (bucket[i]) { 25 ans = Math.min(ans, i - prev); 26 prev = i; 27 } 28 } 29 30 return Math.min(ans, 1440 - prev + first); 31 } 32}
C++ Solution
1 2cpp 3#include <vector> 4#include <string> 5using namespace std; 6 7class Solution { 8public: 9 int findMinDifference(vector<string>& timePoints) { 10 vector<bool> bucket(1440); 11 int first = 1440; 12 int prev = 1440; 13 int ans = 1440; 14 for (string time : timePoints) { 15 int num = stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3)); 16 first = min(first, num); 17 if (bucket[num]) 18 return 0; 19 bucket[num] = true; 20 } 21 22 for (int i = first + 1; i < 1440; i++) { 23 if (bucket[i]) { 24 ans = min(ans, i - prev); 25 prev = i; 26 } 27 } 28 29 return min(ans, 1440 - prev + first); 30 } 31};
JavaScript Solution
1 2javascript 3var findMinDifference = function(timePoints) { 4 let bucket = new Array(1440).fill(false); 5 let first = 1440; 6 let prev = 1440; 7 let ans = 1440; 8 9 for (let time of timePoints) { 10 let [hour, minute] = time.split(":"); 11 let num = parseInt(hour) * 60 + parseInt(minute); 12 first = Math.min(first, num); 13 if (bucket[num]) 14 return 0; 15 bucket[num] = true; 16 } 17 18 for (let i = first + 1; i < 1440; i++) { 19 if (bucket[i]) { 20 ans = Math.min(ans, i - prev); 21 prev = i; 22 } 23 } 24 25 return Math.min(ans, 1440 - prev + first); 26};
C# Solution
1 2csharp 3public class Solution { 4 public int FindMinDifference(IList<string> timePoints) { 5 bool[] bucket = new bool[1440]; 6 int first = 1440; 7 int prev = 1440; 8 int ans = 1440; 9 10 foreach (string time in timePoints) { 11 int hour = Int32.Parse(time.Substring(0, 2)); 12 int minute = Int32.Parse(time.Substring(3)); 13 int num = hour * 60 + minute; 14 first = Math.Min(first, num); 15 if (bucket[num]) { 16 return 0; 17 } 18 bucket[num] = true; 19 } 20 21 for (int i = first + 1; i < 1440; ++i) { 22 if (bucket[i]) { 23 ans = Math.Min(ans, i - prev); 24 prev = i; 25 } 26 } 27 28 return Math.Min(ans, 1440 - prev + first); 29 } 30}
Swift Solution
1
2swift
3class Solution {
4 func findMinDifference(_ timePoints: [String]) -> Int {
5 var bucket: [Bool] = Array(repeating: false, count: 1440)
6 var first = 1440, prev = 1440, ans = 1440
7 for time in timePoints {
8 let (hour, minute) = (Int(time[..<time.index(time.startIndex, offsetBy: 2)])!, Int(time[time.index(time.startIndex, offsetBy: 3)...])!)
9 let num = hour * 60 + minute
10 first = min(first, num)
11 if bucket[num] {
12 return 0
13 }
14 bucket[num] = true
15 }
16 for i in first+1..<1440 {
17 if bucket[i] {
18 ans = min(ans, i - prev)
19 prev = i
20 }
21 }
22 return min(ans, 1440 - prev + first)
23 }
24}
Go Solution
1
2go
3func findMinDifference(timePoints []string) int {
4 bucket := [1440]bool{}
5 var first, prev, ans int = 1440, 1440, 1440
6 for _, time := range timePoints {
7 hour, _ := strconv.Atoi(time[:2])
8 min, _ := strconv.Atoi(time[3:])
9 num := hour*60 + min
10 first = min(first, num)
11 if bucket[num] {
12 return 0
13 }
14 bucket[num] = true
15 }
16 for i := first + 1; i < 1440; i++ {
17 if bucket[i] {
18 ans = min(ans, i-prev)
19 prev = i
20 }
21 }
22 return min(ans, 1440-prev+first)
23}
24func min(a, b int) int {
25 if a < b {
26 return a
27 }
28 return b
29}
In conclusion, the ideal solution will revolve around using a boolean array to keep track of represented minutes. The time difference is then calculated based on the difference between the current time point and the previous one. This method ensures that it covers all possible minute pairs, including the last and first time points. Python, Java, JavaScript, C++, C# solution uses same bucket sort approach to solve the problem. The implementation might vary due to language syntaxes but all keep the main logic intact. Meanwhile, solutions for swift and go are newly introduced. The time complexity of the solution is O(n), where n is number of timePoints. The space complexity will be O(m), m represents 1440 minutes from 24 hours.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.