# Minimum Time Difference
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-time-difference)
Canonical: https://scaleengineer.com/dsa/problems/minimum-time-difference
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, String
**Companies:** [Visa](https://scaleengineer.com/companies/visa), [Zoho](https://scaleengineer.com/companies/zoho), [carwale](https://scaleengineer.com/companies/carwale), [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies)
---
## Problem
Given a list of 24-hour clock time points in **"HH:MM"** format, return _the minimum **minutes** difference between any two time-points in the list_. 

**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 * 104`
* `timePoints[i]` is in the format **"HH:MM"**.

# Approaches
## Brute Force Comparison
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.
**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.
**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.
### Explanation
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.

```java
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]);
    }
}
```
### Algorithm
1. Initialize a variable `minDiff` to a very large value (e.g., `Integer.MAX_VALUE`).
2. Use nested loops to iterate through every unique pair of time points in the input list.
3. For each pair of time strings, convert them into total minutes from midnight (00:00). For a time `HH:MM`, the total minutes are `HH * 60 + MM`.
4. Calculate the absolute difference between the two minute values, let's call it `diff`.
5. Since the clock is circular, the actual difference is the smaller of `diff` and the wrap-around difference, which is `(24 * 60) - diff`.
6. Update `minDiff` with the minimum of its current value and the calculated circular difference.
7. After checking all pairs, return `minDiff`.

## Sorting Approach
A more efficient approach involves sorting. If we convert all time points to minutes and sort them, the minimum difference must occur between two adjacent time points in the sorted list. We just need to iterate through the sorted list once to find the minimum difference between adjacent elements. We also must not forget to check the difference between the first and the last elements, which represents the wrap-around time difference on the clock.
**Time:** O(N log N), dominated by the sorting step. Converting times to minutes takes O(N) and finding the minimum difference after sorting takes another O(N). · **Space:** O(N), to store the list of time points after converting them to minutes. Some sorting algorithms might use additional space.
**Pros:** Much faster than the brute-force approach for larger inputs.; The logic is still relatively straightforward.
**Cons:** Requires O(N) extra space to store the converted minutes.; The time complexity is dominated by sorting, which is not as fast as a linear-time solution.
### Explanation
First, we transform the list of time strings into a list of integers, where each integer is the total number of minutes from midnight. This takes O(N) time. Then, we sort this list of minutes, which takes O(N log N) time. After sorting, the time points are ordered chronologically. The smallest difference will be between consecutive elements. We can find this by iterating through the sorted list and calculating `minutes.get(i) - minutes.get(i-1)`. The final step is to account for the circular clock. The difference between the last time and the first time of the day is also a candidate for the minimum. This is calculated as `(first_time + 24*60) - last_time`. The overall minimum is the minimum of all adjacent differences and this special wrap-around difference.

```java
class Solution {
    public int findMinDifference(java.util.List<String> timePoints) {
        java.util.List<Integer> minutes = new java.util.ArrayList<>();
        for (String time : timePoints) {
            minutes.add(convertToMinutes(time));
        }
        
        java.util.Collections.sort(minutes);
        
        int minDiff = Integer.MAX_VALUE;
        for (int i = 1; i < minutes.size(); i++) {
            minDiff = Math.min(minDiff, minutes.get(i) - minutes.get(i - 1));
        }
        
        // Handle the wrap-around case (difference between the last and first time)
        int wrapAroundDiff = (minutes.get(0) + 24 * 60) - minutes.get(minutes.size() - 1);
        minDiff = Math.min(minDiff, wrapAroundDiff);
        
        return minDiff;
    }

    private int convertToMinutes(String time) {
        String[] parts = time.split(":");
        return Integer.parseInt(parts[0]) * 60 + Integer.parseInt(parts[1]);
    }
}
```
### Algorithm
1. Create a new list to store the time points converted to minutes.
2. Iterate through the input `timePoints` list. For each time string, convert it to total minutes from midnight and add it to the new list.
3. Sort the list of minutes in ascending order.
4. Initialize `minDiff` to a very large value.
5. Iterate through the sorted list from the second element (`i = 1`). Calculate the difference between the current element and the previous one (`minutes[i] - minutes[i-1]`) and update `minDiff` if this difference is smaller.
6. After the loop, handle the wrap-around case. Calculate the difference between the first and last elements: `(minutes[0] + 24 * 60) - minutes[n-1]`.
7. Update `minDiff` one last time with this wrap-around difference.
8. Return `minDiff`.

## Bucket Sort using a Boolean Array
The most optimal approach leverages the fact that there's a fixed, constant number of minutes in a day (1440). We can use a boolean array of size 1440 as a set of buckets, where each index represents a minute of the day. We mark the minutes that are present in the input list. If we encounter a time that's already been marked, the difference is 0. Otherwise, after marking all times, we can iterate through our bucket array to find the smallest gap between two marked minutes. This transforms the problem from comparing input points to scanning a fixed-size array.
**Time:** O(N), where N is the number of time points. We iterate through the input list once (O(N)) and then iterate through the boolean array of constant size 1440 (O(1)). Thus, the total time complexity is dominated by the first pass. · **Space:** O(1), as the size of the boolean array is constant (1440) and does not depend on the size of the input list.
**Pros:** Most efficient with O(N) time complexity.; Uses constant extra space, making it very memory-efficient.
**Cons:** The logic can be slightly more complex to implement correctly, especially handling the pointers for first, previous, and the wrap-around case.
### Explanation
This approach is a form of bucket sort. We create a boolean array of size 1440. First, we handle an edge case: if there are more than 1440 time points, at least two must be the same, so the minimum difference is 0. We then iterate through the input list, convert each time to minutes `m`, and mark the corresponding index `m` in our boolean array as `true`. If we try to mark an index that's already `true`, we've found a duplicate and can immediately return 0. 

If we get through the whole input list without duplicates, we then scan our boolean array from index 0 to 1439. We use pointers `first` (to store the first minute we see) and `prev` (to store the previous minute we saw). As we find `true` values, we calculate the difference from the `prev` one and update our global minimum. Finally, we calculate the wrap-around difference between the `first` and `last` (`prev` will hold the last one) marked minutes and take the minimum. This gives us a linear time solution with constant space.

```java
class Solution {
    public int findMinDifference(java.util.List<String> timePoints) {
        int totalMinutes = 24 * 60;
        if (timePoints.size() > totalMinutes) {
            return 0; // Pigeonhole principle
        }
        
        boolean[] seen = new boolean[totalMinutes];
        for (String time : timePoints) {
            int minutes = Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(3));
            if (seen[minutes]) {
                return 0; // Duplicate time found
            }
            seen[minutes] = true;
        }
        
        int minDiff = Integer.MAX_VALUE;
        int first = -1, prev = -1;
        
        for (int i = 0; i < totalMinutes; i++) {
            if (seen[i]) {
                if (first == -1) {
                    first = i;
                }
                if (prev != -1) {
                    minDiff = Math.min(minDiff, i - prev);
                }
                prev = i;
            }
        }
        
        // Handle wrap-around case
        int wrapAroundDiff = (first + totalMinutes) - prev;
        minDiff = Math.min(minDiff, wrapAroundDiff);
        
        return minDiff;
    }
}
```
### Algorithm
1. Note that there are `24 * 60 = 1440` unique minutes in a day. If the input list has more than 1440 points, by the Pigeonhole Principle, at least two must be identical. In this case, the minimum difference is 0, so we can return immediately.
2. Create a boolean array `seen` of size 1440, initialized to `false`. This array will act as a set of buckets for each minute of the day.
3. Iterate through the input `timePoints`. For each time string:
    a. Convert it to total minutes, `m`.
    b. Check `seen[m]`. If it's `true`, we've found a duplicate time, so return 0.
    c. Otherwise, set `seen[m]` to `true`.
4. After populating the `seen` array, iterate through it from minute 0 to 1439 to find the minimum gap between `true` values.
5. Use variables `first` and `prev` to keep track of the first and previously seen time (minute index).
6. When iterating, if `seen[i]` is `true`, update the `minDiff` with `i - prev` (if `prev` is valid). Then update `prev` to `i`.
7. After the loop, calculate the wrap-around difference between the first and last seen times: `(first + 1440) - prev`.
8. Return the minimum of `minDiff` and the wrap-around difference.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findMinDifference(vector<string> &timePoints) {
    if (timePoints.size() > 24 * 60)
      return 0;
    vector<int> mins;
    for (auto t : timePoints)
      mins.push_back(stoi(t.substr(0, 2)) * 60 + stoi(t.substr(3)));
    sort(mins.begin(), mins.end());
    mins.push_back(mins[0] + 24 * 60);
    int res = 24 * 60;
    for (int i = 1; i < mins.size(); ++i)
      res = min(res, mins[i] - mins[i - 1]);
    return res;
  }
};

```

### Python

```python
''' >>> a = "000" >>> int(a) 0 >>> a = "00011" >>> int(a) 11 ''' class Solution : def findMinDifference ( self , timePoints : List [ str ]) -> int : if len ( timePoints ) > 24 * 60 : return 0 mins = sorted ( int ( t [: 2 ]) * 60 + int ( t [ 3 :]) for t in timePoints ) mins . append ( mins [ 0 ] + 24 * 60 ) # make it a circle, linking 1st and last slot return min ( abs ( a - b ) for a , b in pairwise ( mins )) # below also works, same logic # res = mins[-1] # for i in range(1, len(mins)): # res = min(res, mins[i] - mins[i - 1]) # return res ############ class Solution ( object ): def findMinDifference ( self , timePoints ): """ :type timePoints: List[str] :rtype: int """ ans = 24 * 60 times = [ 0 ] * len ( timePoints ) for i , time in enumerate ( timePoints ): h , m = map ( int , time . split ( ":" )) times [ i ] = h * 60 + m times . sort () for i in range ( len ( times ) - 1 ): ans = min ( ans , abs ( times [ i ] - times [ i + 1 ])) return min ( ans , 1440 - abs ( times [ 0 ] - times [ - 1 ]))
```