Java O(nlog(n))/O(n) Time O(1) Space Solutions


  • 2

    O(nlog(n)) Time O(1) Space:

    public int findMinDifference(List<String> timePoints) {
        Collections.sort(timePoints);
        int minDiff = Integer.MAX_VALUE;
        String prev = timePoints.get(timePoints.size()-1);
        for (String s : timePoints) {
            int prevMins = Integer.parseInt(prev.split(":")[0])*60 + Integer.parseInt(prev.split(":")[1]);
            int curMins = Integer.parseInt(s.split(":")[0])*60 + Integer.parseInt(s.split(":")[1]);
            int diff = curMins - prevMins;
            if (diff < 0) diff += 1440;
            minDiff = Math.min(minDiff, Math.min(diff, 1440 - diff));
            prev = s;
        }
        return minDiff;
    }
    

    O(n) Time O(1) Space. Note that, more accurately, this is O(1) time as the number of iterations of the first loop is limited to 1440 due to the pigeonhole principle.

    public int findMinDifference(List<String> timePoints) {
    
        boolean[] timeSeen = new boolean[1440];
        for (String s : timePoints) {
            int mins = Integer.parseInt(s.split(":")[0])*60 + Integer.parseInt(s.split(":")[1]);
            if (timeSeen[mins]) return 0;
            timeSeen[mins] = true;
        }
        
        Integer firstTimeSeen = null, prevTimeSeen = null, minDiff = Integer.MAX_VALUE;
        for (int i=0;i<1440;i++) {
            if (!timeSeen[i]) continue;
            if (firstTimeSeen == null) {firstTimeSeen = i; prevTimeSeen = i;}
            else {
              minDiff = Math.min(minDiff, Math.min(i - prevTimeSeen, 1440 - i + prevTimeSeen));
              prevTimeSeen = i;
            }
        }
        
        minDiff = Math.min(minDiff, Math.min(prevTimeSeen - firstTimeSeen, 1440 - prevTimeSeen + firstTimeSeen));
        return minDiff;
    }
    

  • 1
    D
    public int findMinDifference(List<String> timePoints) {
    
            boolean[] timeSeen = new boolean[1440];
    
            for (String s : timePoints) {
                int mins = Integer.parseInt(s.split(":")[0]) * 60 + Integer.parseInt(s.split(":")[1]);
                if (timeSeen[mins])
                    return 0;
                timeSeen[mins] = true;
            }
    
            int minDiff = Integer.MAX_VALUE,prev = 0;
    
            for (int i = 1439; i >= 0; i--){
                if(timeSeen[i]){
                    prev = i;
                    break;
                }
            }
    
            for (int i = 0; i < 1440; i++) {
                if(timeSeen[i]){
                    int diff = i - prev;
                    if(diff <0) diff += 1440;
                    minDiff = Math.min(minDiff, diff);
                    prev = i;
                }
            }
    
            return minDiff;
        }
    

    May be it can be read more easily.


  • 0

    Same idea, but finding min diff during sort.

    public int findMinDifference(List<String> list) {
        if(list == null || list.size() == 0) return 0;
        int[] min = new int[] {Integer.MAX_VALUE};
        Collections.sort(list, (a, b) -> {min[0] = Math.min(diff(a, b, 0), min[0]); return a.compareTo(b);});
        return Math.min(min[0], diff(list.get(0), list.get(list.size() - 1), 24 * 60));
    }
    private int diff(String a, String b, int extraMins) {
        String[] aa = a.split(":"), bb = b.split(":");
        int minA = Integer.parseInt(aa[0]) * 60 + Integer.parseInt(aa[1]) + extraMins;
        int minB = Integer.parseInt(bb[0]) * 60 + Integer.parseInt(bb[1]);
        return Math.abs(minA - minB);
    }

Log in to reply
 

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