Java AC 5ms simple solution with detailed explaination


  • 7
    C

    This approach here is trying to find next digit for each postion in "HH:MM" from right to left. If the next digit is greater than current digit, return directly and keep other digits unchanged.
    Here is the steps: (e.g. "17:38")

    1. Retrieve all four digits from given string and sort them in asscending order, "17:38" -> digits[] {'1', '3', '7', '8'}

    2. Apply findNext() from the right most digit to left most digit, try to find next greater digit from digits[] (if exist) which is suitable for current position, otherwise return the minimum digit (digits[0]):

      • "HH:M_": there is no upperLimit for this position (0-9). Just pick the next different digit in the sequence. In the example above, '8' is already the greatest one, so we change it into the smallest one (digits[0] i.e. '1') and move to next step: "17:38" -> "17:31"

      • "HH:_M": the upperLimit is '5' (00~59). The next different digit for '3' is '7', which is greater than '5', so we should omit it and try next. Similarly, '8' is beyond the limit, so we should choose next, i.e. '1': "17:38" -> "17:11"

      • "H_:MM": the upperLimit depends on result[0]. If result[0] == '2', then it should be no more than '3'; else no upperLimit (0-9). Here we have result[0] = '1', so we could choose any digit we want. The next digit for '7' is '8', so we change it and return the result directly. "17:38" -> "18:11"

      • "_H:MM": the upperLimit is '2' (00~23). e.g. "03:33" -> "00:00"

    class Solution {
        
        public String nextClosestTime(String time) {
            char[] result = time.toCharArray();
            char[] digits = new char[] {result[0], result[1], result[3], result[4]};
            Arrays.sort(digits);
            
            // find next digit for HH:M_
            result[4] = findNext(result[4], (char)('9' + 1), digits);  // no upperLimit for this digit, i.e. 0-9
            if(result[4] > time.charAt(4)) return String.valueOf(result);  // e.g. 23:43 -> 23:44
            
            // find next digit for HH:_M
            result[3] = findNext(result[3], '5', digits);
            if(result[3] > time.charAt(3)) return String.valueOf(result);  // e.g. 14:29 -> 14:41
            
            // find next digit for H_:MM
            result[1] = result[0] == '2' ? findNext(result[1], '3', digits) : findNext(result[1], (char)('9' + 1), digits);
            if(result[1] > time.charAt(1)) return String.valueOf(result);  // e.g. 02:37 -> 03:00 
            
            // find next digit for _H:MM
            result[0] = findNext(result[0], '2', digits);
            return String.valueOf(result);  // e.g. 19:59 -> 11:11
        }
        
        /** 
         * find the next bigger digit which is no more than upperLimit. 
         * If no such digit exists in digits[], return the minimum one i.e. digits[0]
         * @param current the current digit
         * @param upperLimit the maximum possible value for current digit
         * @param digits[] the sorted digits array
         * @return 
         */
        private char findNext(char current, char upperLimit, char[] digits) {
            //System.out.println(current);
            if(current == upperLimit) {
                return digits[0];
            }
            int pos = Arrays.binarySearch(digits, current) + 1;
            while(pos < 4 && (digits[pos] > upperLimit || digits[pos] == current)) { // traverse one by one to find next greater digit
                pos++;
            }
            return pos == 4 ? digits[0] : digits[pos];
        }
        
    }
    

  • 1
    M

    brilliant solution! Easy to understand and fast.
    One question though. I think following line has a typo:

    result[1] = digits[0] == '2' ? findNext(result[1], '3', digits) : findNext(result[1], (char)('9' + 1), digits);
    

    instead of digits[0] == '2' shouldn't it be result[0]? Since digits[] are the sorted array, and here we only want to look up for the original time see if it will cause exceeds limit.


  • 0
    C
    This post is deleted!

  • 0
    M

    This answer of 17:38 should be 18:11 instead of 11:11 as you said. Any one can prove if my answer is wrong?


  • 0
    C

    @mol1203 the answer of 17:38 is 18:11. And this is exactly what I said above. :D


  • 0
    S

    Hi, it seems when the input time is 01:11, the first result[0] need to be updated to 10:00.


  • 0
    C

    @shengzhang Thanks for proving my mistake by this case.Since it has been a long time after I first solve this problem, I over-thought it and got a wrong inference. Now I fix it and roll it back to my original solution. Thank you again!


  • 0
    S

    A better way would be to find the highest for each of the digits from right to left and check if it is valid, rather than having multiple if's to fit the solution.

    class Solution {
        public String nextClosestTime(String time) {
            int[] digits = getDigits(time);
            int length = digits.length;
            int[] sorted = Arrays.copyOf(digits, length);
            Arrays.sort(sorted);
            int next = 0;
            
            for(int i = length - 1; i >= 0; --i) {
                next = nextHighest(sorted, digits[i]);
                
                if(next > digits[i]) {
                    digits[i] = next;
                    if(isValid(digits)) {
                        break;
                    } else {
                        digits[i] = sorted[0];
                    }
                } else {
                    digits[i] = sorted[0];
                }
            }
            
            return String.format("%02d:%02d", digits[0] * 10 + digits[1], digits[2] * 10 + digits[3]);
        }
        
        public int[] getDigits(String time) {
            String[] parts = time.split(":");
            int[] digits = new int[4];
            int index = 0;
            int cur = 0;
            
            for(String s : parts) {
                cur = Integer.parseInt(s);
                digits[index++] = cur / 10;
                digits[index++] = cur % 10;
            }
            
            return digits;
        }
        
        public int nextHighest(int[] sorted, int cur) {
            for(int num : sorted) {
                if(num > cur) {
                    return num;
                }
            }
            
            return cur;
        }
        
        public boolean isValid(int[] digits) {
            if(digits[0] * 10 + digits[1] < 24 && digits[2] * 10 + digits[3] < 60) {
                return true;
            }
            
            return false;
        }
    }
    

  • 0
    D

    @cwleoo Hi, could you help me analyze the runtime of your solution?
    Is it O(nlogn), since we have O(logn) binary search operation, in each iteration of the for loop, in the worst case.

    I'm considering the while loop in the findNext() function to be constant time, since at worse it can be O(4).

    Could someone confirm or correct me?

    ~Thanks


Log in to reply
 

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