539. Minimum Time Difference

Given a list of 24-hour clock time points in "Hour:Minutes" format, find the minimum minutes difference between any two time points in the list.

Example 1:

Input: ["23:59","00:00"]
Output: 1

Note:

1. The number of time points in the given list is at least 2 and won't exceed 20000.

2. The input time is legal and ranges from 00:00 to 23:59.

int findMinDifference(vector<string>& timePoints) { // time: O(n); space: O(1)
    vector<bool> buckets(24 * 60, false);
    for (const string& t : timePoints) {
        int pos = t.find(":");
        int cur = stoi(t.substr(0, pos)) * 60 + stoi(t.substr(pos + 1));
        if (buckets[cur]) return 0; // duplicate
        buckets[cur] = true;
    }
    int prev = -1, first = numeric_limits<int>::max(), last = numeric_limits<int>::min(), res = numeric_limits<int>::max();
    for (int i = 0; i < buckets.size(); ++i) {
        if (buckets[i]) {
            if (prev != -1) res = min(res, i - prev);
            prev = i;
            first = min(first, i);
            last = max(last, i);
        }
    }
    res = min(res, first - last + 24 * 60);
    return res;
}