Java AC 5ms simple solution with detailed explaination


  • 3
    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": no need to change it. To prove that, thinking about all possible situations, and there are ONLY two cases:

        1. It never been hit because we already found the result and returned it when checking previous digits; (e.g.: 21:39 -> 22:11, the first '2' is not touched.)
        2. We do need to check this digit, which means that we replace all three previous digits with digits[0]. This situation happens if and only if result[0] == digits[0]. Transparently there is no need to change it as the result is guaranteed the same. (e.g.: 19:59 -> 11:11)
    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 -- No need to change
            // 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

    Yes, you are right. And thanks to you, I found this fact:

    • Whatever input string is, result[0] never changes.

    To prove that, thinking about all possible situations, and there are ONLY two cases:

    1. It never been hit because we already found the result and returned it when checking previous digits; (e.g.: 21:39 -> 22:11, the first 2 is not touched.)
    2. We do need to check this digit, which means that we replace all three previous digits with digits[0]. This situation happens if and only if result[0] == digits[0]. Transparently there is no need to change it as the result is guaranteed the same. (e.g.: 19:59 -> 11:11)

    And it also explains why the typo doesn't lead to a wrong answer. I've fixed it and updated my explaination accordingly. Thank you for pointing it out! : )


Log in to reply
 

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