Verbose Java Solution, Bucket


  • 32

    There is only 24 * 60 = 1440 possible time points. Just create a boolean array, each element stands for if we see that time point or not. Then things become simple...

    public class Solution {
        public int findMinDifference(List<String> timePoints) {
            boolean[] mark = new boolean[24 * 60];
            for (String time : timePoints) {
                String[] t = time.split(":");
                int h = Integer.parseInt(t[0]);
                int m = Integer.parseInt(t[1]);
                if (mark[h * 60 + m]) return 0;
                mark[h * 60 + m] = true;
            }
            
            int prev = 0, min = Integer.MAX_VALUE;
            int first = Integer.MAX_VALUE, last = Integer.MIN_VALUE;
            for (int i = 0; i < 24 * 60; i++) {
                if (mark[i]) {
                    if (first != Integer.MAX_VALUE) {
                        min = Math.min(min, i - prev);
                    }
                    first = Math.min(first, i);
                    last = Math.max(last, i);
                    prev = i;
                }
            }
            
            min = Math.min(min, (24 * 60 - last + first));
            
            return min;
        }
    }
    

  • 4

    same idea here but you can improve your time a little if you avoid string split and int parse. You know the input format so you can leverage that directly. Also I break out the wrap around time difference rather than doing it in the same loop.

        public int FindMinDifference(IList<string> timePoints) {
            bool[] axis = new bool[24 * 60];
            foreach (string t in timePoints)
            {
                int hour = 10 * (t[0] - '0') + (t[1] - '0');
                int minute = 10 * (t[3] - '0') + (t[4] - '0');
                int index = hour * 60 + minute;
                
                if (axis[index]) return 0; // duplicate
                
                axis[index] = true;
            }
            
            int min = axis.Length;
            int curr = axis.Length;
            for (int i = 0; i < axis.Length; i++)
            {
                if (axis[i])
                {
                    if (curr < min) min = curr;
                    curr = 1;
                }
                else 
                {
                    curr++;
                }
            }
            
            // now check wrap around time diff
            int dist = 1;
            int first = 0;
            while (!axis[first]) { first++; dist++; }
            
            int last = axis.Length - 1;
            while (!axis[last]) { last--; dist++; }
            
            if (dist < min) min = dist;
            
            return min;
        }
    

  • 0
    M

    Why the last statement for updating min i.e.
    min = Math.min(min, (24 * 60 - last + first));


  • 2

    @mishabhi It only calculates i - prev during the loop. At last, we need to take care the last and first time points. i.e. [00:00, 10:00, 23:00]. The smallest gap is between 23:00 and 00:00.


  • 7
    Z

    My Idea is the same, but instead of updating min at the end, min = Math.min(min, (24 * 60 - last + first)); I have expanded the time frame twice. Despite it is a little bit slower, I have decided to share

    public class Solution {
        public int findMinDifference(List<String> timePoints) {
            if(timePoints == null || timePoints.isEmpty()) return 0;
            boolean [] minutes = new boolean[2*24*60];
            for(String time:timePoints){
                String tokens[]  = time.split(":");
                int minute = Integer.parseInt(tokens[0])*60+Integer.parseInt(tokens[1]);
                if(minutes[minute]) return 0;
                minutes[minute] = true;
                int nextDayMinute = minute+60*24;
                minutes[nextDayMinute] = true;
            }
            int prev = -100000;
            int min = Integer.MAX_VALUE;
            for(int i = 0;i<minutes.length;i++){
                if(minutes[i]){
                    min = Math.min(i-prev, min);
                    prev = i;
                }
            }
            return min;
        }
    }

  • 1
    I

    14ms

            int[] buckets = new int[24 * 60];
            int ans = 24 * 60, first = ans;
            for (String hhmm : timePoints) {
                int num = 60 * Integer.parseInt(hhmm.substring(0, 2));
                num += Integer.parseInt(hhmm.substring(3));
                first = Math.min(first, num);
                if (++buckets[num] > 1) return 0; // same bucket
            }
            int prev = first;
            for (int i = first + 1; i < buckets.length; ++i) {
                if (buckets[i] == 0) continue;
                ans = Math.min(ans, i - prev);
                prev = i;
            }
            return Math.min(ans, 24 * 60 + first - prev);
    

  • 1
    Q

    My solution bucket solution in C++ is similar, besides some small optimizations.
    which being copyed as below.

    bucket solution in C++, short-circuitif duplicate exist or lengh > 720

    1. pigeon hole short-circuit, if length > 1440 return 0;
    2. use flag array, if duplicate, return 0;
    3. pigeon hole short-circuit, if length > 1440 / 2 return 1;
    4. check minimal difference, similar to Verbose Java Solution, Bucket
      4.1 short-circuit if res reach 1
    int findMinDifference(vector<string>& timePoints) {
        if (timePoints.size() > 1440) return 0; 
        std::vector<int> times(1440, 0);
        auto getTime = [](string t) { return 60 * ((t[0] - '0') * 10 + (t[1] - '0')) + ((t[3] - '0') * 10 + (t[4] - '0')); };
        for (int i = 0, sz = std::min(timePoints.size(), times.size()); i < sz; ++i) {
            if (times[getTime(timePoints[i])]++) return 0;
        }
        if (timePoints.size() > 1440 / 2) return 1; 
        int res = 1440, prev = -1440, first = -1440;
        // for (int i = 0, sz = times.size(); i < sz; ++i) {
        for (int i = 0, sz = times.size(); i < sz && res > 1; ++i) {
            if (times[i]) {
                if (first < 0) first = i;
                res = std::min(res, i - prev);
                prev = i;
            }
        }
        res = std::min(res, 1440 - (prev - first));  // handle `last - first` case
        return res;
    }

  • 0
    B

    excellent observation! bucket
    that eliminates the sort operation needed.


  • 2

    Thanks for sharing! Can we make use of radix sorting here to decrease the space complexity?

    public int findMinDifference(List<String> timePoints) {
            int n = timePoints.size();
            int[] ts = new int[n];
            for (int i = 0; i < n; i++) { // Convert date to minutes format
                String[] hhmm = timePoints.get(i).split(":");
                ts[i] = Integer.valueOf(hhmm[0]) * 60 + Integer.valueOf(hhmm[1]);
            }
            
            for (int d = 0; d < 4; d++) { // Perform radix sorting
                ts = countingSort(ts, d);    
            }
            
            int min = Integer.MAX_VALUE;
            for (int i = 1; i < n; i++) { // Compare adjacent time
                min = Math.min(min, ts[i] - ts[i - 1]);
            }
            min = Math.min(min, 1440 - (ts[n - 1] - ts[0]));
            return min;
        }
         
        private int[] countingSort(int[] ts, int d) {
            // Count number of occurance of each digit
            int[] cnt = new int[10];
            for (int t : ts) {
                for (int i = 0; i < d; i++) t /= 10; // Get digit value
                cnt[t % 10]++;
            }
    
            // Add up number of occurance into position in final output
            for (int i = 1; i < cnt.length; i++) cnt[i] += cnt[i - 1];
    
            // Place each number on its position
            int n = ts.length;
            int[] ret = new int[n];
            for (int i = n - 1; i >= 0; i--) {
                int t = ts[i];
                for (int j = 0; j < d; j++) t /= 10;
                ret[--cnt[t % 10]] = ts[i]; // off-by-one
            }
            return ret;
        }
    

  • 0
    K

    @shawngao My implementation beats 97% of Java submissions, although I can't claim to know why:

    public class Solution {
        public int findMinDifference(List<String> timePoints) {
            boolean[] times = new boolean[1440];
            for (String timeString : timePoints) {
                int minutes = convertToMinutes(timeString);
                if (times[minutes]) {
                    return 0;
                }
                times[minutes] = true;
            }
            
            int minimum = Integer.MAX_VALUE;
            int first = -1;
            int prev = -1;
            for (int i = 0; i < times.length; i ++) {
                if (!times[i]) {
                    continue;
                }
                
                if (prev == -1) {
                    prev = i;
                    first = i;
                    continue;
                }
                
                int distance = i - prev;
                distance = Math.min(1440 - distance, distance);
                minimum = Math.min(minimum, distance);
                prev = i;
            }
            
            // take the difference of first and last
            minimum = Math.min(minimum, first + 1440 - prev);
            
            return minimum;
        }
        
        private int convertToMinutes(String timeString) {
            return (60 * Integer.valueOf(timeString.substring(0, 2))) + Integer.valueOf(timeString.substring(3));
        }
    }
    

  • 0
    B

    @shawngao said in Verbose Java Solution, Bucket:

    min = Math.min(min, (24 * 60 - last + first));

    To explain it in my words, this is done to handle tests cases like [00:00, 10:00, 23:00] that @shawngao mentioned above. By keep track of the last and the first entry in the boolean array (indexed by minutes), we try to work on the edge cases centered around 12 o'clock. Please correct me if my understanding is incorrect. Thanks!


  • 0
        public int findMinDifference(List<String> timePoints) {
           boolean[] b = new boolean[24 * 60]; 
           for(String point: timePoints){
              String[] time = point.split(":");
              int m = Integer.parseInt(time[0]) * 60 + Integer.parseInt(time[1]);
              if(b[m]) return 0; 
              b[m] = true;  
           } 
           
           int pre = - 24 * 60, res = 24 * 60;
           int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE; 
           for(int i = 0; i < 24 * 60; i++){
              if(b[i]){
                res = Math.min(i - pre, res);
                max = Math.max(i, max);  
                min = Math.min(i, min);    
                pre = i;    
              } 
           } 
           res = Math.min(min + 24 * 60 - max, res); 
           return res; 
        }

  • 0
    Y

    @shawngao Thanks for sharing. Instead of using parseInt, I used charAt() - '0'. The following code can beat 99% in OJ.

    public int findMinDifference(List<String> timePoints) {
            boolean[] mark = new boolean[24 * 60];
            for(String timePoint : timePoints) {
                int hour = (timePoint.charAt(0) - '0') * 10 + (timePoint.charAt(1) - '0');
                int minute = (timePoint.charAt(3) - '0') * 10 + (timePoint.charAt(4) - '0');
                if(mark[hour * 60 + minute]) return 0;
                mark[hour * 60 + minute] = true;
            }
            
            int min = Integer.MAX_VALUE, prev = 0;
            int first = Integer.MAX_VALUE, last = Integer.MIN_VALUE;
            for(int i = 0; i < 24 * 60; i++) {
                if(mark[i]) {
                    if(first != Integer.MAX_VALUE) {
                        min = Math.min(min, i - prev);
                    }
                    first = Math.min(first, i);
                    last = Math.max(last, i);
                    prev = i;
                }
            }
            min = Math.min(min, 24 * 60 + first - last);
            return min;
        }
    

Log in to reply
 

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