Bruteforce Algorithm to Find the Next Closet Time Reusing the Current Digits

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.

How to Find the Next Closet Time Reusing the Current Digits?

The first step is to parse the given time string and this should allow us extracting the four digit values. Starting from the current time, we can increment the time at each step one minute forward, and check if all digits are re-used.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    string nextClosestTime(string time) {
        int h1 = time[0] - '0';
        int h2 = time[1] - '0';
        int m1 = time[3] - '0';
        int m2 = time[4] - '0';
        int h = h1 * 10 + h2;
        int m = m1 * 10 + m2;
        unordered_set<int> digits({h1, h2, m1, m2});
        for (;;) {
            m ++;
            if (m == 60) {
                m = 0;
                h = (h + 1) % 24;
            }            
            if ((digits.count(m % 10)) && 
                (digits.count(h % 10)) && 
                (digits.count(m / 10)) && 
                (digits.count(h / 10))) {
                return std::to_string(h/10) + 
                    std::to_string(h%10) + ":" +
                    std::to_string(m/10) + 
                    std::to_string(m%10);
            }
        }        
        return ""; // make compiler happy
    }
};

class Solution {
public:
    string nextClosestTime(string time) {
        int h1 = time[0] - '0';
        int h2 = time[1] - '0';
        int m1 = time[3] - '0';
        int m2 = time[4] - '0';
        int h = h1 * 10 + h2;
        int m = m1 * 10 + m2;
        unordered_set<int> digits({h1, h2, m1, m2});
        for (;;) {
            m ++;
            if (m == 60) {
                m = 0;
                h = (h + 1) % 24;
            }            
            if ((digits.count(m % 10)) && 
                (digits.count(h % 10)) && 
                (digits.count(m / 10)) && 
                (digits.count(h / 10))) {
                return std::to_string(h/10) + 
                    std::to_string(h%10) + ":" +
                    std::to_string(m/10) + 
                    std::to_string(m%10);
            }
        }        
        return ""; // make compiler happy
    }
};

when minute goes to 60, we should wrap it to zero and increment the hour – and when hour goes to 24, we should rewind it to zero. The complexity for this particular bruteforce algorithm is O(1) as we will at most iterate 24*60 and the time complexity is O(1) as well, as we use a set to store at most 4 values.

–EOF (The Ultimate Computing & Technology Blog) —