# LC 539. Minimum Time Difference

### [Problem link](https://leetcode.com/problems/minimum-time-difference/)

###### tags: `leedcode` `medium` `c++` `Bucket Sort`

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:**

- <code>2 <= timePoints.length <= 2 * 10⁴</code>
- <code>timePoints[i]</code> is in the format **"HH:MM"** .

## Solution 1
#### C++

class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        vector<int> time(timePoints.size());
        for (int i = 0; i < timePoints.size(); i++) {
            int hour = stoi(timePoints[i].substr(0, 2));
            int min = stoi(timePoints[i].substr(3, 2));
            time[i] = hour * 60 + min;
        }

        sort(time.begin(), time.end());
        int ans = INT_MAX;
        for (int i = 1; i < time.size(); i++) {
            ans = min(ans, time[i] - time[i - 1]);
        }
        ans = min(ans, 24 * 60 - time.back() + time[0]);

        return ans;
    }
};

## Solution 2 - Bucket Sort
#### C++

class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        vector<bool> mins(24 * 60, false);
        for (int i = 0; i < timePoints.size(); i++) {
            int hour = stoi(timePoints[i].substr(0, 2));
            int min = stoi(timePoints[i].substr(3, 2));
            int time = hour * 60 + min;
            if (mins[time] == true) {
                return 0;
            }
            mins[time] = true;
        }

        int pre = INT_MAX;
        int first = INT_MAX;
        int last = INT_MAX;
        int ans = INT_MAX;
        for (int i = 0; i < mins.size(); i++) {
            if (mins[i] == true) {
                if (pre != INT_MAX) {
                    ans = min(ans, i - pre);
                }
                pre = i;
                if (first == INT_MAX) {
                    first = i;
                }
                last = i;
            }
        }
        ans = min(ans, 24 * 60 - last + first);

        return ans;
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(nlogn) | O(n) |
>| Solution 2 | O(n) | O(1) |

## Note
Sol2:
排序的最小最大值都是固定的，可以用O(n)來達成跟排序O(nlogn)一樣的功能。

1. 有出現過的時間都設成true, 如果時間已經出現過, 則return 0.
2. 用三個指標pre, first, last紀錄前一個出現的時間, 第一個出現的時間，最後一個出現的時間
3. 遍歷mins更新pre, first, last, ans
4. 最後比較ans跟頭尾的時間差距(24 * 60 - last + first)