Verbose Java Solution, Bucket


  • 39

    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;
        }
    }
    

  • 6

    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;
        }
    

  • 1
    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!


  • 1
        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;
        }
    

  • 0
    M

    @shawngao thanks for sharing. A C++ version:

        int findMinDifference(vector<string>& timePoints) {
            int n = 24 * 60;
            vector<char> mp(n, false);
            for(auto& t : timePoints){
                int pos = stoi(t.substr(0, 2)) * 60 + stoi(t.substr(3, 2));
                if(mp[pos]) return 0;
                mp[pos] = true;
            }
            
            int diff = INT_MAX, pre = -1, first = INT_MAX, last = INT_MIN;
            for(int i = 0; i < n; ++i){
                if(mp[i]){
                    if(pre != -1)
                        diff = min(diff, min(i - pre, pre + n - i));
                    first = min(first, i);
                    last = max(last, i);
                    pre = i;
                }            
            }
            return min(diff, min(last - first, first + n - last));
        }
    

  • 0

    Great solution as usual!!

    Here's my solution. It's a sort based solution. I try to find min during sort. It's definitely slow, and additional 70 ms because of lamba.

    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);
    }

  • 0
    A

    Thats a neat trick! Thanks for posting.
    Another solution based on this technique:
    Using a BitSet instead of a boolean array. Saves space.

        public int findMinDifference(List<String> timePoints) {
            
            BitSet timeMap = new BitSet(1440);
            
            //flag all the times that are present in the array
            //if we get a repeat time, then we can say thay the min distance is 0
            for(String time: timePoints){
                int index = getTimeIndex(time);
                if(timeMap.get(index)==true)
                    return 0;
                timeMap.set(index);
            }
            
            //find position of the first time
            int i = 0;
            while(timeMap.get(i++)==false);
            int firstBit = i-1;
            
            //get min distance between two set bits
            int min = 1440,count = 0;
            for(;i<1440;i++){
                if(timeMap.get(i)==false){
                    count++;
                }else{
                    min = Math.min(min,count+1);
                    count = 0;
                }
            }
            
            //find position of the last time
            while(timeMap.get(i--)==false);
            int lastBit = i+1;
            
            //position of the first and last set bits are used to check for rollover min distances like 23:59 and 00:01
            int rollOverDistance = ((1440-lastBit)+firstBit);
            min = Math.min(min,rollOverDistance);
            return min;
            
        }
        
        public int getTimeIndex(String time){
            int h1 = time.charAt(0)-'0';
            int h0 = time.charAt(1)-'0';
            int m1 = time.charAt(3)-'0';
            int m0 = time.charAt(4)-'0';
            int h = h1*10+h0;
            int m = m1*10+m0;
            return 60*h+m;
        }
    }```

  • 0
    C

    @shawngao hi, i have a question about the last statement, why you need 2460 - last + first, not last - fast. I think you let "last" to represent the last time and "first" represent the first time, so the difference between these two time should be last minus first, why you put 24 60 - last + first. Ty for your help


Log in to reply
 

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