Minimum Time Difference

Problem

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:

• The number of time points in the given list is at least 2 and won't exceed 20000.
• The input time is legal and ranges from 00:00 to 23:59.

Solution

Convert to Unique Time in Minutes Solution

public class Solution {
    public int findMinDifference(List<String> timePoints) {
        int[] times = new int[24 * 60];
        for (String time : timePoints) {
            int index = time.indexOf(":");
            int hour = Integer.parseInt(time.substring(0, index));
            int min = Integer.parseInt(time.substring(index + 1));
            if(times[hour * 60 + min]++ > 0) return 0; //Do not forget to check duplicated times  
        }

        int first = -1, last = 0, min = Integer.MAX_VALUE;
        int prev = 0;
        for (int i = 0; i < times.length; i++) {
            if (times[i] == 0) continue;
            if (first == -1) {
                first = i;
                prev = i;
            }
            else {
                min = Math.min(i - prev, min);
                prev = i;
                last = i;
            }
        }

        return Math.min(min, first + times.length - last);
    }
}

Analysis

The key idea of this solution is to have an array recording each time in minutes int[24 * 60]
Then we loop through each time and increase the int[hour * 60 + min]
We return 0 immediately if we find two same times
Otherwise, we get the min time using another for loop
Notice that the very first time and last time can be minimal because time rounds in circle
Hence we need to have first and last to store them and return Math.min(min, first + length - last) at the end