539. Minimum Time Difference (Medium)

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.

Solution 1: Hash Table, Bucket Sort 16ms

class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        bool mark[1440] = {false}; // 24*60 = 1440
        for (auto& t: timePoints) {
            int spot = stoi(t.substr(0,2))*60+stoi(t.substr(3));
            if (mark[spot]) return 0;
            mark[spot] = true;
        }
        int prev = -1, res = 1440;
        int first = -1, last = -1;
        for (int i = 0; i < 1440; ++i) {
            if (mark[i]) {
                if (first == -1) { // find first timepoint
                    first = i;
                } else { 
                    res = min(res, i-prev);
                    last = max(last, i);
                }
                prev = i;
            }
        }
        return min(res, 1440-(last-first));
    }
};

Solution 2: 23ms

class Solution {
    int StrToMinutes(string t) {
        return stoi(t.substr(0,2))*60+stoi(t.substr(3));
    }
public:
    int findMinDifference(vector<string>& timePoints) {
        int n = timePoints.size(), res = 1440;
        sort(timePoints.begin(), timePoints.end());
        int prev = StrToMinutes(timePoints[n-1]), cur = 0;
        for (int i = 0; i < n; ++i) {
            cur = StrToMinutes(timePoints[i]);
            int diff = abs(cur-prev);
            diff = min(diff,1440-diff);
            res = min(res, diff);
            prev = cur;
        }
        return res;
    }
};