681. Next Closest Time
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:
-
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. -
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 between00
and23
, and minutes are between00
and59
. -
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, andd
to keep track of the smallest time difference observed.
Algorithm Steps:
-
Initialization: Convert the time
HH:MM
into total minutes to facilitate easy comparison, disregard colon, and prepare a set of unique digits. -
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.
- The
-
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
and0 <= minutes < 60
).
- 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 (
-
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) andd
(the difference between the current time and the candidate time).
- For every valid time formed that is strictly after the current time and closer than any previous valid times, update
-
Finding the Minimum Time for Edge Cases:
- If no valid time is found which is closer than a day (which means
ans
isNone
), we find the smallest digit in the set and fill the time with that smallest digit to formHH:MM
. This is essentially the earliest time for the next day using the available digits.
- If no valid time is found which is closer than a day (which means
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through the solution with a small example: Assume the current time given is 19:34
.
- 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}
.
- 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.
- Checking Validity:
- For instance, one possible combination the DFS algorithm may come up with is
13:49
. Thecheck
function parses13
as hours and49
as minutes and confirms it's a valid time.
- Updating the Closest Time:
- We then convert
13:49
into total minutes:(13 * 60) + 49 = 829
minutes. - We calculate the time difference
d
between1174
(original time) and829
(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 time1174
, and since this is the first valid time we've encountered that is later than the current time, we setans
to19:41
andd
to1181 - 1174 = 7
minutes.
- Continuing the DFS:
- The DFS continues, and say it next finds
14:13
. It is a valid time, but it's earlier than19:34
when we convert it to total minutes. - If the DFS explores all combinations and finds no better time than
19:41
, thenans
remains19:41
.
- 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 digit1
in{1, 3, 4, 9}
, and constructing the next time as11: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.
Solution Implementation
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
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
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
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 most4^4
. Even though we writeO(4^4)
to represent the total number of DFS calls, it simplifies toO(1)
because4^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.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!