O(nlogn + n) solution


  • 0

    If we sort the list first, then min diff can be found easily by comparing ONLY adjacent items in the list. There is 1 extra comparison that is needed after this : the round the clock diff between the first and last elements of the sorted list.

    public class Solution {
        public int findMinDifference(List<String> timePoints) {
            Collections.sort(timePoints);
            int minMinuteDiff = Integer.MAX_VALUE;
            for(int i = 0; i < timePoints.size() - 1; i++) {
                int minuteDiff = Math.abs(getMinutes(timePoints.get(i)) - getMinutes(timePoints.get(i + 1)));
                minMinuteDiff = (minuteDiff < minMinuteDiff) ? minuteDiff : minMinuteDiff;
            }
            String firstTimePoint = timePoints.get(0);
            String lastTimePoint = timePoints.get(timePoints.size() - 1);
            int roundTheClockDiff = (getMinutes("24:00") - getMinutes(lastTimePoint)) 
                + (getMinutes(firstTimePoint) - getMinutes("00:00"));
            minMinuteDiff = (roundTheClockDiff < minMinuteDiff) ? roundTheClockDiff : minMinuteDiff;
            
            return minMinuteDiff;
        }
        
        private int getMinutes(String timePoint) {
            int indexOfSep = 2;
            int hours = Integer.parseInt(timePoint.substring(0, indexOfSep));
            int minutes = Integer.parseInt(timePoint.substring(indexOfSep + 1));
            return (hours * 60 + minutes);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.