681. Next Closest Time

MediumStringEnumeration
Leetcode Link

Problem Description

The problem requires us to find the next closest time that can be formed by reusing the digits in the given time in the format HH:MM. The key constraints are that the time is always valid, is in 24-hour format, and the next time must be the closest future time – this means that if the current time is 23:59 and the only digit available is 9, the next closest time is 22:22, which is actually the closest next day time as the clock loops back.

The challenge involves figuring out the combination of digits that would not only form a valid time but also is closest to the current time among all the valid candidates.

Intuition

The solution hinges on these key steps:

  1. Generating All Possible Times: We need to try out all combinations of the given digits to form a valid HH:MM time. This is akin to generating permutations with repetition allowed, since it does not matter how many times a digit is reused.

  2. Validating the Time: Not all permutations will result in a valid time. For example, 26:74 is not a valid time. We must ensure that hours are between 00 and 23, and minutes are between 00 and 59.

  3. Finding the Next Closest Time: Among the valid times, we must find the one that is closest to the original time given, yet strictly after it, considering time as cyclic.

To accomplish this, a depth-first search (DFS) algorithm is applied in the solution:

  • The DFS function builds a time candidate, digit by digit, only keeping valid time candidates. When a 4-digit string is constructed, it is checked for validity.
  • Valid times are then compared to the original time to check if they are closer. The difference d between the current time and the candidate is used for this purpose.
  • The global variable ans holds the current best solution.

The code handles the edge case where no time is strictly closer by the digits given, such as 22:22 then the smallest digit available is repeated in the format HH:MM to make the next valid time, which technically is the next day's time (as in the case where time is 23:59 and the only digit available is 9, resulting in 22:22).

Solution Approach

The implementation of the solution uses a recursive algorithm known as depth-first search (DFS), which explores all possible times that can be composed using the given digits.

Data Structures Used:

  • A set called s collects distinct digits from the input time, which will aid in crafting the next possible times.
  • Variables such as ans to keep track of the answer, and d to keep track of the smallest time difference observed.

Algorithm Steps:

  1. Initialization: Convert the time HH:MM into total minutes to facilitate easy comparison, disregard colon, and prepare a set of unique digits.

  2. Depth-First Search (DFS):

    • The dfs function is recursively called to construct every possible combination of the digits. As it is called, it forms strings representing possible times (as 4-digit strings, ignoring colons).
    • Once a full time (4 digits) is formed, it gets validated by the check function, which ensures that the hours and minutes are within their respective valid ranges.
  3. Checking Validity:

    • When a complete 4-digit representation is formed, the function parses the first two characters as hours and the last two as minutes and then checks if they make a valid time (0 <= hours < 24 and 0 <= minutes < 60).
  4. Updating the Closest Time:

    • For every valid time formed that is strictly after the current time and closer than any previous valid times, update ans (next closest time) and d (the difference between the current time and the candidate time).
  5. Finding the Minimum Time for Edge Cases:

    • If no valid time is found which is closer than a day (which means ans is None), we find the smallest digit in the set and fill the time with that smallest digit to form HH:MM. This is essentially the earliest time for the next day using the available digits.

Once the process is completed, the solution exists in ans, which then is formatted accordingly into a time string HH:MM and returned.

DFS Function Usage:

This DFS function is a common pattern used in backtracking problems to check all possible configurations and find a solution that meets certain criteria. By employing recursion, the algorithm can build upon partial solutions (in this case, partial times), backtrack if a certain path doesn't lead to a solution, and continue exploring until the solution is found.

The choice of recursion and the DFS approach is suitable here because the number of total possible times that can be formed with the given digits is limited, which allows a brute force method to be used without significant performance concerns.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's walk through the solution with a small example: Assume the current time given is 19:34.

  1. Initialization:
  • Convert 19:34 to total minutes: (19 * 60) + 34 = 1174 minutes.
  • Extract and store the unique digits from the time: {1, 3, 4, 9}.
  1. Depth-First Search (DFS):
  • We begin to construct possible times using the digits in {1, 3, 4, 9} through recursion. Our DFS will attempt every possible 4-digit combination using these digits.
  1. Checking Validity:
  • For instance, one possible combination the DFS algorithm may come up with is 13:49. The check function parses 13 as hours and 49 as minutes and confirms it's a valid time.
  1. Updating the Closest Time:
  • We then convert 13:49 into total minutes: (13 * 60) + 49 = 829 minutes.
  • We calculate the time difference d between 1174 (original time) and 829 (potential next closest time). Since 829 is less than 1174, it represents an earlier time, so we continue searching.
  • Now let's say the DFS generates 19:41. It's a valid time, and in minutes, it is (19 * 60) + 41 = 1181. This time is later than our current time 1174, and since this is the first valid time we've encountered that is later than the current time, we set ans to 19:41 and d to 1181 - 1174 = 7 minutes.
  1. Continuing the DFS:
  • The DFS continues, and say it next finds 14:13. It is a valid time, but it's earlier than 19:34 when we convert it to total minutes.
  • If the DFS explores all combinations and finds no better time than 19:41, then ans remains 19:41.
  1. Finding the Minimum Time for Edge Cases:
  • Suppose no valid time was found that was later than 19:34 (which isn't the case in our example). Then, the algorithm would proceed to the edge case step, taking the minimum digit 1 in {1, 3, 4, 9}, and constructing the next time as 11:11, indicating the next available time in a new day.

In the end, given our example, the algorithm would yield 19:41 as the next closest time created by using the digits from the original time 19:34. This time is just 7 minutes later, which makes it the closest next valid time by using the original digits.

Python Solution

1class Solution:
2    def nextClosestTime(self, time: str) -> str:
3        # Helper function to check if time is valid
4        def is_valid(time_str):
5            hours, minutes = int(time_str[:2]), int(time_str[2:])
6            return 0 <= hours < 24 and 0 <= minutes < 60
7
8        # Depth-first search to find the next closest time
9        def dfs(current):
10            if len(current) == 4:
11                if not is_valid(current):
12                    return
13                nonlocal closest_time, time_diff
14                current_minutes = int(current[:2]) * 60 + int(current[2:])
15                if initial_minutes < current_minutes < initial_minutes + time_diff:
16                    time_diff = current_minutes - initial_minutes
17                    closest_time = current[:2] + ':' + current[2:]
18                return
19            for char in unique_chars:
20                dfs(current + char)
21
22        # Set of unique characters in the input time and initialization
23        unique_chars = {char for char in time if char != ':'}
24        initial_minutes = int(time[:2]) * 60 + int(time[3:])
25        infinity = float('inf')
26        time_diff = infinity
27        closest_time = None
28
29        # Perform DFS to find the next closest time
30        dfs('')
31
32        # If no valid time is found, return the earliest possible time
33        if closest_time is None:
34            min_char = min(unique_chars)
35            closest_time = f'{min_char}{min_char}:{min_char}{min_char}'
36
37        return closest_time
38

Java Solution

1class Solution {
2    private int originalTotalMinutes;
3    private int minDifference;
4    private String answer;
5    private Set<Character> validDigits;
6
7    // This method finds the next closest time using the digits of the given time.
8    public String nextClosestTime(String time) {
9        // Convert the given time to total minutes.
10        originalTotalMinutes = Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(3));
11        // Initialize the minimum difference to a large value.
12        minDifference = Integer.MAX_VALUE;
13        // Create a set to store the unique digits from the time.
14        validDigits = new HashSet<>();
15        // Tracks the minimum digit.
16        char minDigit = '9';
17        for (char c : time.toCharArray()) {
18            if (c != ':') {
19                validDigits.add(c);
20                if (c < minDigit) {
21                    minDigit = c;
22                }
23            }
24        }
25        answer = null;
26        // Begin deep first search to build valid times.
27        deepFirstSearch("");
28        // If no answer was found in the search, use the smallest digit four times to create the earliest possible time.
29        if (answer == null) {
30            answer = "" + minDigit + minDigit + ":" + minDigit + minDigit;
31        }
32        return answer;
33    }
34
35    // Helper method to perform deep first search over the possible times.
36    private void deepFirstSearch(String current) {
37        // When the current string is 4 digits long, we have a complete time.
38        if (current.length() == 4) {
39            if (!isValidTime(current)) {
40                return;
41            }
42            int potentialTimeMinutes
43                = Integer.parseInt(current.substring(0, 2)) * 60 + Integer.parseInt(current.substring(2));
44            // Check if the potential time is closer to the original time.
45            if (potentialTimeMinutes > originalTotalMinutes && potentialTimeMinutes - originalTotalMinutes < minDifference) {
46                minDifference = potentialTimeMinutes - originalTotalMinutes;
47                answer = current.substring(0, 2) + ":" + current.substring(2);
48            }
49            return;
50        }
51        // Recurse for each valid digit to build the time string.
52        for (char c : validDigits) {
53            deepFirstSearch(current + c);
54        }
55    }
56
57    // Helper method to check if a string represents a valid time.
58    private boolean isValidTime(String timeStr) {
59        int hour = Integer.parseInt(timeStr.substring(0, 2));
60        int minute = Integer.parseInt(timeStr.substring(2));
61        return 0 <= hour && hour < 24 && 0 <= minute && minute < 60;
62    }
63}
64

C++ Solution

1#include <string>
2#include <set>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8private:
9    int originalTotalMinutes;
10    int minDifference;
11    string answer;
12    set<char> validDigits;
13
14    // Helper method to check if a string represents a valid time.
15    bool isValidTime(const string& timeStr) {
16        int hour = stoi(timeStr.substr(0, 2));
17        int minute = stoi(timeStr.substr(2));
18        return hour >= 0 && hour < 24 && minute >= 0 && minute < 60;
19    }
20
21    // Helper method to perform depth first search over the possible times.
22    void depthFirstSearch(const string& current) {
23        // When the current string is 4 digits long, a complete time is formed.
24        if (current.length() == 4) {
25            if (!isValidTime(current)) {
26                return;
27            }
28            int potentialTimeMinutes = stoi(current.substr(0, 2)) * 60 + stoi(current.substr(2));
29            // Check if the potential time is closer to the original time.
30            if (potentialTimeMinutes > originalTotalMinutes &&
31                potentialTimeMinutes - originalTotalMinutes < minDifference) {
32                minDifference = potentialTimeMinutes - originalTotalMinutes;
33                answer = current.substr(0, 2) + ":" + current.substr(2);
34            }
35            return;
36        }
37        // Recurse for each valid digit to build the time string.
38        for (char c : validDigits) {
39            depthFirstSearch(current + c);
40        }
41    }
42
43public:
44    // This method finds the next closest time using the digits of the given time.
45    string nextClosestTime(string time) {
46        // Convert the given time to total minutes.
47        originalTotalMinutes = stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3));
48        // Initialize the minimum difference to a large value.
49        minDifference = INT_MAX;
50        char minDigit = '9';
51        // Create a set to store the unique digits from the time.
52        for (char c : time) {
53            if (c != ':') {
54                validDigits.insert(c);
55                if (c < minDigit) {
56                    minDigit = c;
57                }
58            }
59        }
60        answer = "";
61        // Begin depth first search to build valid times.
62        depthFirstSearch("");
63        // If no answer was found in the search, use the smallest digit four times to create the earliest possible time.
64        if (answer.empty()) {
65            answer = string(2, minDigit) + ":" + string(2, minDigit);
66        }
67        return answer;
68    }
69};
70

Typescript Solution

1// Declare global variables
2let originalTotalMinutes: number;
3let minDifference: number;
4let answer: string;
5let validDigits: Set<string>;
6
7// Converts the input time to total minutes since midnight
8function convertToMinutes(time: string): number {
9    const hours = parseInt(time.substring(0, 2), 10);
10    const minutes = parseInt(time.substring(3), 10);
11    return hours * 60 + minutes;
12}
13
14// Determines if a given time string represents a valid time
15function isValidTime(timeStr: string): boolean {
16    const hour = parseInt(timeStr.substring(0, 2), 10);
17    const minute = parseInt(timeStr.substring(2), 10);
18    return hour >= 0 && hour < 24 && minute >= 0 && minute < 60;
19}
20
21// Performs deep first search over the possible times
22function deepFirstSearch(current: string): void {
23    // When the current string is 4 digits long, a complete time is formed
24    if (current.length === 4) {
25        if (!isValidTime(current)) {
26            return;
27        }
28
29        const potentialTotalMinutes = convertToMinutes(current.substring(0, 2) + ':' + current.substring(2));
30      
31        // Check if the potential time is closer to the original time but only if it's later
32        if (potentialTotalMinutes > originalTotalMinutes && potentialTotalMinutes - originalTotalMinutes < minDifference) {
33            minDifference = potentialTotalMinutes - originalTotalMinutes;
34            answer = current.substring(0, 2) + ':' + current.substring(2);
35        }
36        return;
37    }
38
39    // Recursively append valid digits to build the time string
40    validDigits.forEach((digit: string) => {
41        deepFirstSearch(current + digit);
42    });
43}
44
45// This method finds the next closest time using the digits of the given time
46function nextClosestTime(time: string): string {
47    originalTotalMinutes = convertToMinutes(time);
48
49    minDifference = Number.MAX_SAFE_INTEGER;
50    validDigits = new Set<string>();
51
52    // Find the minimum digit for use in case no valid time is found
53    let minDigit: string = '9';
54    for (const c of time) {
55        if (c !== ':') {
56            validDigits.add(c);
57            minDigit = c < minDigit ? c : minDigit;
58        }
59    }
60
61    answer = null;
62
63    // Begin deep first search to build valid times
64    deepFirstSearch('');
65
66    // If no valid time was found, create the earliest possible time using the smallest digit
67    if (answer === null) {
68        answer = minDigit + minDigit + ':' + minDigit + minDigit;
69    }
70
71    return answer;
72}
73
74// Example usage:
75// const closestTime = nextClosestTime('19:34');
76// console.log(closestTime); // Outputs the next closest time using the same digits
77

Time and Space Complexity

The given Python code finds the next closest time that can be formed by reusing the current digits. To achieve this, it uses depth-first search (DFS) combined with a check to ensure valid time formation. Let's analyze the time and space complexity:

Time Complexity:

The algorithm iterates through every possibility of the time by DFS, where each level of recursion represents one digit of the time string, excluding the colon. Since there are at most 4 digits and each digit can be one of the 4 different digits from the original time, the maximum number of recursive calls is 4^4. However, the 'check()' function is called for every complete time generated to confirm its validity, and this check operation is constant time, thus we have the following time complexity:

  • Worst-case time complexity: O(1), since the number of permutations is finite and at most 4^4. Even though we write O(4^4) to represent the total number of DFS calls, it simplifies to O(1) because 4^4 is a constant.

Space Complexity:

As for the space complexity, the max depth of recursion DFS call stack would be 4, and the space to hold the 'ans', 'current', and temporary variables inside the DFS function. Moreover, the set 's' stores at most 4 elements. Therefore, the space complexity will be:

  • Space complexity: O(1), for the DFS call stack and auxiliary variables and the set 's', all of which have a constant bound.
😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫