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 and first 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 previous first. 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 updates ans to the smaller value between the current ans and the difference between the current minute and prev. 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 current ans and 24 * 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.