Next Closest Time

Problem

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.

Examples

Example 1:

1
2
3
4


Input: time = "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:

1
2
3
4


Input: time = "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.

Constraints:

time.length == 5
time is a valid time in the form "HH:MM".
0 <= HH < 24
0 <= MM < 60

Solution

Method 1 -

Intuition

We need to find the next time (in minutes) that can be formed using only the digits in the current time. Since there are only 4 digits, we can brute-force all possible times and pick the next closest one.

Approach

Extract the digits from the input time. Generate all possible combinations for hours and minutes using these digits. For each valid time, compute its total minutes since midnight. Find the one with the smallest positive difference from the current time.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


string nextClosestTime(string time) {
    int cur = stoi(time.substr(0,2)) * 60 + stoi(time.substr(3,2));
    set<char> digits(time.begin(), time.end());
    digits.erase(':');
    int minDiff = 1440, res = cur;
    for (char h1 : digits) for (char h2 : digits) for (char m1 : digits) for (char m2 : digits) {
        int hour = (h1-'0')*10 + (h2-'0');
        int minute = (m1-'0')*10 + (m2-'0');
        if (hour < 24 && minute < 60) {
            int total = hour*60 + minute;
            int diff = (total - cur + 1440) % 1440;
            if (diff > 0 && diff < minDiff) {
                minDiff = diff; res = total;
            }
        }
    }
    char buf[6];
    sprintf(buf, "%02d:%02d", res/60, res%60);
    return string(buf);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func nextClosestTime(time string) string {
    cur := (int(time[0]-'0')*10+int(time[1]-'0'))*60 + int(time[3]-'0')*10 + int(time[4]-'0')
    digits := []byte{time[0], time[1], time[3], time[4]}
    minDiff, res := 1440, cur
    for _, h1 := range digits {
        for _, h2 := range digits {
            for _, m1 := range digits {
                for _, m2 := range digits {
                    hour := int(h1-'0')*10 + int(h2-'0')
                    minute := int(m1-'0')*10 + int(m2-'0')
                    if hour < 24 && minute < 60 {
                        total := hour*60 + minute
                        diff := (total - cur + 1440) % 1440
                        if diff > 0 && diff < minDiff {
                            minDiff = diff; res = total
                        }
                    }
                }
            }
        }
    }
    return fmt.Sprintf("%02d:%02d", res/60, res%60)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


public String nextClosestTime(String time) {
    int cur = Integer.parseInt(time.substring(0,2)) * 60 + Integer.parseInt(time.substring(3,5));
    Set<Character> digits = new HashSet<>();
    for (char c : time.toCharArray()) if (c != ':') digits.add(c);
    int minDiff = 1440, res = cur;
    for (char h1 : digits) for (char h2 : digits) for (char m1 : digits) for (char m2 : digits) {
        int hour = (h1-'0')*10 + (h2-'0');
        int minute = (m1-'0')*10 + (m2-'0');
        if (hour < 24 && minute < 60) {
            int total = hour*60 + minute;
            int diff = (total - cur + 1440) % 1440;
            if (diff > 0 && diff < minDiff) {
                minDiff = diff; res = total;
            }
        }
    }
    return String.format("%02d:%02d", res/60, res%60);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


fun nextClosestTime(time: String): String {
    val cur = time.substring(0,2).toInt() * 60 + time.substring(3,5).toInt()
    val digits = time.filter { it != ':' }.toSet()
    var minDiff = 1440; var res = cur
    for (h1 in digits) for (h2 in digits) for (m1 in digits) for (m2 in digits) {
        val hour = (h1-'0')*10 + (h2-'0')
        val minute = (m1-'0')*10 + (m2-'0')
        if (hour < 24 && minute < 60) {
            val total = hour*60 + minute
            val diff = (total - cur + 1440) % 1440
            if (diff > 0 && diff < minDiff) {
                minDiff = diff; res = total
            }
        }
    }
    return "%02d:%02d".format(res/60, res%60)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


def nextClosestTime(time: str) -> str:
    cur = int(time[:2]) * 60 + int(time[3:])
    digits = set(time.replace(':', ''))
    min_diff, res = 1440, cur
    for h1 in digits:
        for h2 in digits:
            for m1 in digits:
                for m2 in digits:
                    hour = int(h1) * 10 + int(h2)
                    minute = int(m1) * 10 + int(m2)
                    if hour < 24 and minute < 60:
                        total = hour * 60 + minute
                        diff = (total - cur + 1440) % 1440
                        if 0 < diff < min_diff:
                            min_diff = diff
                            res = total
    return f"{res//60:02d}:{res%60:02d}"

 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


fn next_closest_time(time: &str) -> String {
    let cur = time[0..2].parse::<u32>().unwrap() * 60 + time[3..5].parse::<u32>().unwrap();
    let digits: Vec<char> = time.chars().filter(|&c| c != ':').collect();
    let mut min_diff = 1440;
    let mut res = cur;
    for &h1 in &digits {
        for &h2 in &digits {
            for &m1 in &digits {
                for &m2 in &digits {
                    let hour = h1.to_digit(10).unwrap() * 10 + h2.to_digit(10).unwrap();
                    let minute = m1.to_digit(10).unwrap() * 10 + m2.to_digit(10).unwrap();
                    if hour < 24 && minute < 60 {
                        let total = hour * 60 + minute;
                        let diff = (total + 1440 - cur) % 1440;
                        if diff > 0 && diff < min_diff {
                            min_diff = diff;
                            res = total;
                        }
                    }
                }
            }
        }
    }
    format!("{:02}:{:02}", res/60, res%60)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


function nextClosestTime(time: string): string {
    const cur = parseInt(time.slice(0,2)) * 60 + parseInt(time.slice(3));
    const digits = Array.from(new Set(time.replace(':', '').split('')));
    let minDiff = 1440, res = cur;
    for (const h1 of digits) for (const h2 of digits) for (const m1 of digits) for (const m2 of digits) {
        const hour = parseInt(h1) * 10 + parseInt(h2);
        const minute = parseInt(m1) * 10 + parseInt(m2);
        if (hour < 24 && minute < 60) {
            const total = hour * 60 + minute;
            const diff = (total - cur + 1440) % 1440;
            if (diff > 0 && diff < minDiff) {
                minDiff = diff; res = total;
            }
        }
    }
    return `${String(Math.floor(res/60)).padStart(2, '0')}:${String(res%60).padStart(2, '0')}`;
}

Complexity

⏰ Time complexity: O(1) (at most 4^4 = 256 combinations).
🧺 Space complexity: O(1).

Problem#

Examples#

Solution#

Method 1 -#

Intuition#

Approach#

Code#

Complexity#