539. Minimum Time Difference

time difference is also a circular problem, so just append data with 24hours again, it works

sort + circular array

T: O(nlogn)

S: O(n)

class Solution {
    public int findMinDifference(List<String> timePoints) {
        
        List<Integer> times = new ArrayList<>();
        for (String time : timePoints) {
            String hourStr = time.substring(0, 2);
            int hour = Integer.valueOf(hourStr);
            int min = Integer.valueOf(time.substring(3, 5));
            times.add(hour*60+min);
            times.add((hour+24)*60+min); // append data with 24*60 = 1440 (one more 24 hours cycle)
        }
        
        Collections.sort(times);
        
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < times.size() - 1; i++) {
            res = Math.min(res, times.get(i+1) - times.get(i));
        }
        return res;
    }
}

/*
return the minimum "minutes" difference

0000
0001

2400

2259
1111


0010

2359

["00:00","23:59", 2400]

*/

sort

or just calculate last one and first one case

res = Math.min(res, 1440 - times.get(times.size()-1) + times.get(0));

class Solution {
    public int findMinDifference(List<String> timePoints) {
        
        List<Integer> times = new ArrayList<>();
        for (String time : timePoints) {
            String hourStr = time.substring(0, 2);
            int hour = Integer.valueOf(hourStr);
            int min = Integer.valueOf(time.substring(3, 5));
            times.add(hour*60+min);
            // times.add((hour+24)*60+min); // append data with 24*60 = 1440 (one more 24 hours cycle)
        }
        
        Collections.sort(times);
        
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < times.size() - 1; i++) {
            res = Math.min(res, times.get(i+1) - times.get(i));
        }
        
        res = Math.min(res, 1440 - times.get(times.size()-1) + times.get(0));
        return res;
    }
}

bucket

T: O(n), n is size of timePoints

S: O(1)

class Solution {
    public int findMinDifference(List<String> timePoints) {
        boolean[] bucket = new boolean[1440];
        int first = Integer.MAX_VALUE;
        int last = 0;
        
        for (String time : timePoints) {
            int hour = Integer.valueOf(time.substring(0, 2));
            int min = Integer.valueOf(time.substring(3, 5));
            
            int timeIdx = hour*60 + min;
            if (bucket[timeIdx]) { // if has duplicate time, means diff is 0
                return 0;
            }
            bucket[timeIdx] = true;
            first = Math.min(first, timeIdx); // record first, last time 
            last = Math.max(last, timeIdx);
        }
        
        
        int count = 0;
        int prev = 0;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < 1440; i++) {
            if (bucket[i]) { // if bucket has time
                if (count == 0) {
                    prev = i;
                }
                
                if (count != 0) {
                    res = Math.min(res, i - prev); // curr time - prev time
                    prev = i;
                }
                count++;
            }
        }
        res = Math.min(res, 1440 - last + first);
        
        return res;
    }
}