Next Closest Time

Medium

Given a time represented in the format "HH:MM", form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused.

You may assume the given input string is always valid. For example, "01:34", "12:09" are all valid. "1:34", "12:9" are all invalid.

Example 1:

Input: "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, 
    which occurs 5 minutes later.  It is not 19:33, because this occurs 23 hours and 59 minutes later.

Example 2:

Input: "23:59"
Output: "22:22"
Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. 
    It may be assumed that the returned time is next day's time since it is smaller than the input time numerically.

Analysis

难度不在思维，而是在实现，要严谨周全。

Solution

@cwleoo

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. ApplyfindNext()from the right most digit to left most digit, try to find next greater digit fromdigits[](if exist) which is suitable for current position, otherwise return the minimum digit (digits[0]):

3. "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"

4. "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"

5. "H_:MM": the upperLimit depends onresult[0]. Ifresult[0] == '2', then it should be no more than'3'; else no upperLimit (0-9). Here we haveresult[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"

6. "_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];
    }

}

LeetCode Official Solutions

Simulation

Simulate the clock going forward by one minute. Each time it moves forward, if all the digits are allowed, then return the current time.

The natural way to represent the time is as an integertin the range0 <= t < 24 * 60. Then the hours aret / 60, the minutes aret % 60, and each digit of the hours and minutes can be found byhours / 10, hours % 10etc.

Complexity Analysis

• Time Complexity: O(1). We try up to 24 * 60 possible times until we find the correct time.

• Space Complexity: O(1).

class Solution {
    public String nextClosestTime(String time) {
        int cur = 60 * Integer.parseInt(time.substring(0, 2));
        cur += Integer.parseInt(time.substring(3));
        Set<Integer> allowed = new HashSet();
        for (char c: time.toCharArray()) if (c != ':') {
            allowed.add(c - '0');
        }

        while (true) {
            cur = (cur + 1) % (24 * 60);
            int[] digits = new int[]{cur / 60 / 10, cur / 60 % 10, cur % 60 / 10, cur % 60 % 10};
            search : {
                for (int d: digits) if (!allowed.contains(d)) break search;
                return String.format("%02d:%02d", cur / 60, cur % 60);
            }
        }
    }
}

Build From Allowed Digits

We have up to 4 different allowed digits, which naively gives us4 * 4 * 4 * 4possible times. For each possible time, let's check that it can be displayed on a clock: ie.,hours < 24 and mins < 60. The best possibletime != startis the one with the smallestcand_elapsed = (time - start) % (24 * 60), as this represents the time that has elapsed sincestart, and where the modulo operation is taken to be always non-negative.

For example, if we havestart = 720(ie. noon), then times like12:05 = 725means that(725 - 720) % (24 * 60) = 5seconds have elapsed; while times like00:10 = 10means that(10 - 720) % (24 * 60) = -710 % (24 * 60) = 730seconds have elapsed.

Also, we should make sure to handlecand_elapsedcarefully. When our current candidate timecuris equal to the given starting time, thencand_elapsedwill be0and we should handle this case appropriately.

• Time Complexity: O(1). We all4^444possible times and take the best one.

• Space Complexity: O(1).

class Solution {
    public String nextClosestTime(String time) {
        int start = 60 * Integer.parseInt(time.substring(0, 2));
        start += Integer.parseInt(time.substring(3));
        int ans = start;
        int elapsed = 24 * 60;
        Set<Integer> allowed = new HashSet();
        for (char c: time.toCharArray()) if (c != ':') {
            allowed.add(c - '0');
        }

        for (int h1: allowed) for (int h2: allowed) if (h1 * 10 + h2 < 24) {
            for (int m1: allowed) for (int m2: allowed) if (m1 * 10 + m2 < 60) {
                int cur = 60 * (h1 * 10 + h2) + (m1 * 10 + m2);
                int candElapsed = Math.floorMod(cur - start, 24 * 60);
                if (0 < candElapsed && candElapsed < elapsed) {
                    ans = cur;
                    elapsed = candElapsed;
                }
            }
        }

        return String.format("%02d:%02d", ans / 60, ans % 60);
    }
}

Reference

https://leetcode.com/problems/next-closest-time/solution/