O(n) time complexity, clear Java solution


  • -1
    H

    The basic idea is very clear.

    1. Store all times into an array with values converted to minutes (1 hour = 60 minutes)
    2. Sort the array in an ascending order
    3. Pick up each minute value and compare it with its previous time and its next time
    4. When comparing, we use +/- 1440 minutes to offset the time when its prev or next is over or before 00:00. This part is a little bit tricky.
    5. Since it only uses two loops, so the time complexity is O(n)
    public class Solution {
        public int findMinDifference(List<String> timePoints) {
            int[] minutes = new int[timePoints.size()];
            for(int i = 0; i < minutes.length; i++) {
                String time = timePoints.get(i);
                String[] parts = time.split(":");
                minutes[i] = Integer.valueOf(parts[0]) * 60 + Integer.valueOf(parts[1]);
            }
            Arrays.sort(minutes);
            int min = Integer.MAX_VALUE;
            for(int i = 0; i < minutes.length; i++) {
                int next = (i + 1) % minutes.length;
                int prev = i - 1 < 0 ? minutes.length - 1 : i - 1;
                min = Math.min(min, Math.abs(minutes[i] - minutes[prev]));
                min = Math.min(min, Math.abs(minutes[i] + 1440 - minutes[prev]));
                min = Math.min(min, Math.abs(minutes[next] - minutes[i]));
                min = Math.min(min, Math.abs(minutes[next] - 1440 - minutes[next]));
            }
            
            return min;
        }
    }
    

  • 0
    S

    You are using Arrays.sort() - the time complexity of which is O(nlogn), so time complexity of your solution is O(nlogn).


Log in to reply
 

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