Jobs

Interviews

Discussions

Next Closest Time

Medium

Google

6 views

Topics:

Strings

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 are allowed to rearrange the digits, and you must use all four digits.

Produce the next closest time in the format "HH:MM".

Example 1:

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:31, because this occurs 23 hours and 57 minutes later.

Example 2:

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 the nearest.

Constraints:

The input time is a valid time represented in the format "HH:MM".

Try coding it in LeetCode

Next Closest Time

Medium

Google

6 views

Topics:

Strings

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 are allowed to rearrange the digits, and you must use all four digits.

Produce the next closest time in the format "HH:MM".

Example 1:

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:31, because this occurs 23 hours and 57 minutes later.

Example 2:

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 the nearest.

Constraints:

The input time is a valid time represented in the format "HH:MM".

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the format of the input time? Specifically, is it always a string in "HH:MM" format?
Are all possible digits (0-9) guaranteed to be present in the input time string?
If the next closest time is the same as the input time (after cycling through all possible combinations of the digits), should I return the input time or the next occurrence of that same time?
What is the expected behavior if the input time is invalid, for example, "25:00"?
Is the time represented in 24-hour format or 12-hour format?

Brute Force Solution

Approach

The brute force approach to finding the next closest time involves generating every possible time using the digits from the input time. Then, we check each generated time to see if it's valid and later than the input time. Finally, we pick the smallest valid time that is later than the input.

Here's how the algorithm would work step-by-step:

First, extract the allowed digits from the given time. For example, if the time is 19:34, the allowed digits are 1, 9, 3, and 4.
Next, systematically create every possible combination of hours and minutes using only those allowed digits. This means trying every digit for the first hour digit, then every digit for the second hour digit, and so on, until you have a complete time.
For each of these generated times, check if it's a valid time. A valid time needs to have hours between 00 and 23, and minutes between 00 and 59.
If a generated time is valid, compare it to the original input time. We're looking for the closest time *after* the original time.
If the valid generated time is later than the original time, save it as a potential answer.
Once you've checked all possible generated times, look at all the potential answers you've saved. Find the potential answer that is closest to the original time. This is your final answer.

Code Implementation

def next_closest_time(time):
    allowed_digits = set(time[:2] + time[3:])

    current_hour = int(time[:2])
    current_minute = int(time[3:])

    closest_time = None

    for first_digit in allowed_digits:
        for second_digit in allowed_digits:
            for third_digit in allowed_digits:
                for fourth_digit in allowed_digits:
                    possible_hour = int(first_digit + second_digit)
                    possible_minute = int(third_digit + fourth_digit)

                    # We need to make sure the generated time is valid
                    if possible_hour >= 0 and possible_hour <= 23 and \
                       possible_minute >= 0 and possible_minute <= 59:

                        possible_time_total_minutes = possible_hour * 60 + possible_minute
                        current_time_total_minutes = current_hour * 60 + current_minute

                        if possible_time_total_minutes > current_time_total_minutes:
                            if closest_time is None:
                                closest_time = "%02d:%02d" % (possible_hour, possible_minute)

                            else:
                                closest_hour = int(closest_time[:2])
                                closest_minute = int(closest_time[3:])
                                closest_time_total_minutes = closest_hour * 60 + closest_minute

                                if possible_time_total_minutes < closest_time_total_minutes:
                                    closest_time = "%02d:%02d" % (possible_hour, possible_minute)

    # If no time is greater, find the smallest time possible
    if closest_time is None:
        allowed_digits_list = sorted(list(allowed_digits))
        closest_time = allowed_digits_list[0] + allowed_digits_list[0] + ":" + allowed_digits_list[0] + allowed_digits_list[0]

    return closest_time

Big(O) Analysis

Time Complexity

O(1) – The algorithm generates all possible 4-digit times using the allowed digits. Since the number of allowed digits is at most 4, the number of possible times generated is 4*4*4*4 = 256, which is constant. Checking each generated time for validity and closeness to the original time also takes constant time. Therefore, the overall time complexity is O(1) because the number of operations does not depend on the input size, but rather a fixed number of possibilities given the problem constraints.

Space Complexity

O(1) – The algorithm generates all possible times using the digits from the input time. While it implicitly explores combinations, it doesn't explicitly store all generated times in a data structure that scales with the input. The potential answer is stored in a single variable. Therefore, the auxiliary space used is constant regardless of the input time, resulting in O(1) space complexity.

Optimal Solution

Approach

The goal is to find the smallest time that can be formed using the digits from the given time, and that is also later than the given time. Instead of checking every possible time combination, we can build the next closest time digit by digit, starting from the rightmost digit.

Here's how the algorithm would work step-by-step:

Extract the individual digits that are present in the given time.
Starting from the rightmost digit (the seconds place), try to find the next largest digit that is also present in the extracted digits, but does not cause that part of the time to be invalid (e.g., seconds cannot exceed 59).
If such a digit is found, replace the current digit with it, and you're done because this will be the closest valid time.
If no such digit is found for the rightmost digit, set it to the smallest available digit from the extracted digits and move to the next digit to the left (the tens of seconds place).
Repeat the process of finding the next largest valid digit for each position, moving from right to left.
If you reach the leftmost digit (the tens of hours place) and still cannot find a larger valid digit, set it to the smallest available digit. This indicates that you must 'wrap around' to the beginning of the next day.
After wrapping around (if necessary), set all digits to the right to the smallest digit to form the absolute smallest time from the given digits.
Combine the digits into the new time format and return it.

Code Implementation

def next_closest_time(time):
    current_hour = int(time[0:2])
    current_minute = int(time[3:5])
    digits = {time[0], time[1], time[3], time[4]}
    all_possible_times = sorted(hour + ':' + minute
                               for hour in (d1 + d2 for d1 in digits for d2 in digits)
                               for minute in (d3 + d4 for d3 in digits for d4 in digits)
                               if hour <= '23' and minute <= '59')
    current_time = time[0:2] + ':' + time[3:5]
    next_time = min(t for t in all_possible_times if t > current_time, default=all_possible_times[0])
    return next_time

def next_closest_time_original(time):
    available_digits = sorted(set(time))
    available_digits.remove(':')
    current_hour = int(time[:2])
    current_minute = int(time[3:])

    while True:
        current_minute += 1
        if current_minute == 60:
            current_minute = 0
            current_hour += 1
            if current_hour == 24:
                current_hour = 0

        hour_string = str(current_hour).zfill(2)
        minute_string = str(current_minute).zfill(2)
        new_time = hour_string + minute_string

        is_valid = True
        for digit in new_time:
            if digit not in available_digits:
                is_valid = False
                break

        if is_valid:
            return hour_string + ':' + minute_string

def next_closest_time_detailed(time):
    available_digits = sorted(set(time))
    available_digits.remove(':')

    hour_tens = int(time[0])
    hour_ones = int(time[1])
    minute_tens = int(time[3])
    minute_ones = int(time[4])

    while True:
        minute_ones = find_next_greater(minute_ones, available_digits, 9)

        if minute_ones is None:
            minute_ones = int(available_digits[0])
            minute_tens = find_next_greater(minute_tens, available_digits, 5)

            if minute_tens is None:
                minute_tens = int(available_digits[0])
                hour_ones = find_next_greater(hour_ones, available_digits, 9 if hour_tens < 2 else 3)

                if hour_ones is None:
                    hour_ones = int(available_digits[0])
                    hour_tens = find_next_greater(hour_tens, available_digits, 2)

                    if hour_tens is None:
                        # We need to start over from the smallest possible time
                        hour_tens = int(available_digits[0])
                        hour_ones = int(available_digits[0])
                       minute_tens = int(available_digits[0])
                        minute_ones = int(available_digits[0])
       
        hour = hour_tens * 10 + hour_ones
        if hour < 24:
            #Ensure this is a valid hour before returning.
            break
    return str(hour_tens) + str(hour_ones) + ':' + str(minute_tens) + str(minute_ones)

def find_next_greater(current_digit, available_digits, limit):
    for digit in available_digits:
        digit = int(digit)
        if digit > current_digit and digit <= limit:
            return digit
    return None

Big(O) Analysis

Time Complexity

O(1) – The algorithm iterates through the digits of the time string (HH:MM), which has a fixed length of 4 digits. For each digit, it iterates through a maximum of 4 possible digits extracted from the original time. Therefore, the number of operations is bounded by a constant. Since the input size is limited and the loops iterate a fixed number of times, the time complexity does not scale with increasing input size and is considered O(1).

Space Complexity

O(1) – The algorithm extracts the digits from the input time, which creates a fixed-size collection of 4 digits. It also utilizes a few integer variables for iterating through the digits and potentially storing the smallest digit. Regardless of the input time, the space required for these variables remains constant; therefore the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input time string	Return null or throw IllegalArgumentException, as a valid time cannot be derived.
Input time string is invalid format (e.g., missing colon, incorrect length)	Throw IllegalArgumentException as parsing will fail and the time digits cannot be extracted.
All digits in the input time are the same (e.g., '11:11')	The algorithm must correctly find the next valid time using this single available digit by wrapping around when needed.
The provided digits cannot form a valid time (e.g., digits are 4, 5, 6, 7)	The algorithm should wrap around to the smallest possible valid time that can be formed with available digits, like '00:00' if 0 is available.
Input time is '23:59'	The next closest time must correctly wrap around to the earliest possible time composed of available digits.
Integer overflow when calculating possible next times	The algorithm should use string manipulation to avoid integer overflow when generating and comparing times.
Time contains non-digit characters	Throw an exception, or filter down to valid digit characters and continue.
Only one unique digit is provided, and that digit can only be used in one location, creating an impossible scenario for some time components	Algorithm should handle constraints such as the tens place for hours only having a digit from 0-2 available within the provided digits.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the format of the input time? Specifically, is it always a string in "HH:MM" format?
Are all possible digits (0-9) guaranteed to be present in the input time string?
If the next closest time is the same as the input time (after cycling through all possible combinations of the digits), should I return the input time or the next occurrence of that same time?
What is the expected behavior if the input time is invalid, for example, "25:00"?
Is the time represented in 24-hour format or 12-hour format?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, extract the allowed digits from the given time. For example, if the time is 19:34, the allowed digits are 1, 9, 3, and 4.
Next, systematically create every possible combination of hours and minutes using only those allowed digits. This means trying every digit for the first hour digit, then every digit for the second hour digit, and so on, until you have a complete time.
For each of these generated times, check if it's a valid time. A valid time needs to have hours between 00 and 23, and minutes between 00 and 59.
If a generated time is valid, compare it to the original input time. We're looking for the closest time *after* the original time.
If the valid generated time is later than the original time, save it as a potential answer.
Once you've checked all possible generated times, look at all the potential answers you've saved. Find the potential answer that is closest to the original time. This is your final answer.

Code Implementation

def next_closest_time(time):
    allowed_digits = set(time[:2] + time[3:])

    current_hour = int(time[:2])
    current_minute = int(time[3:])

    closest_time = None

    for first_digit in allowed_digits:
        for second_digit in allowed_digits:
            for third_digit in allowed_digits:
                for fourth_digit in allowed_digits:
                    possible_hour = int(first_digit + second_digit)
                    possible_minute = int(third_digit + fourth_digit)

                    # We need to make sure the generated time is valid
                    if possible_hour >= 0 and possible_hour <= 23 and \
                       possible_minute >= 0 and possible_minute <= 59:

                        possible_time_total_minutes = possible_hour * 60 + possible_minute
                        current_time_total_minutes = current_hour * 60 + current_minute

                        if possible_time_total_minutes > current_time_total_minutes:
                            if closest_time is None:
                                closest_time = "%02d:%02d" % (possible_hour, possible_minute)

                            else:
                                closest_hour = int(closest_time[:2])
                                closest_minute = int(closest_time[3:])
                                closest_time_total_minutes = closest_hour * 60 + closest_minute

                                if possible_time_total_minutes < closest_time_total_minutes:
                                    closest_time = "%02d:%02d" % (possible_hour, possible_minute)

    # If no time is greater, find the smallest time possible
    if closest_time is None:
        allowed_digits_list = sorted(list(allowed_digits))
        closest_time = allowed_digits_list[0] + allowed_digits_list[0] + ":" + allowed_digits_list[0] + allowed_digits_list[0]

    return closest_time

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Extract the individual digits that are present in the given time.
Starting from the rightmost digit (the seconds place), try to find the next largest digit that is also present in the extracted digits, but does not cause that part of the time to be invalid (e.g., seconds cannot exceed 59).
If such a digit is found, replace the current digit with it, and you're done because this will be the closest valid time.
If no such digit is found for the rightmost digit, set it to the smallest available digit from the extracted digits and move to the next digit to the left (the tens of seconds place).
Repeat the process of finding the next largest valid digit for each position, moving from right to left.
If you reach the leftmost digit (the tens of hours place) and still cannot find a larger valid digit, set it to the smallest available digit. This indicates that you must 'wrap around' to the beginning of the next day.
After wrapping around (if necessary), set all digits to the right to the smallest digit to form the absolute smallest time from the given digits.
Combine the digits into the new time format and return it.

Code Implementation

def next_closest_time(time):
    current_hour = int(time[0:2])
    current_minute = int(time[3:5])
    digits = {time[0], time[1], time[3], time[4]}
    all_possible_times = sorted(hour + ':' + minute
                               for hour in (d1 + d2 for d1 in digits for d2 in digits)
                               for minute in (d3 + d4 for d3 in digits for d4 in digits)
                               if hour <= '23' and minute <= '59')
    current_time = time[0:2] + ':' + time[3:5]
    next_time = min(t for t in all_possible_times if t > current_time, default=all_possible_times[0])
    return next_time

def next_closest_time_original(time):
    available_digits = sorted(set(time))
    available_digits.remove(':')
    current_hour = int(time[:2])
    current_minute = int(time[3:])

    while True:
        current_minute += 1
        if current_minute == 60:
            current_minute = 0
            current_hour += 1
            if current_hour == 24:
                current_hour = 0

        hour_string = str(current_hour).zfill(2)
        minute_string = str(current_minute).zfill(2)
        new_time = hour_string + minute_string

        is_valid = True
        for digit in new_time:
            if digit not in available_digits:
                is_valid = False
                break

        if is_valid:
            return hour_string + ':' + minute_string

def next_closest_time_detailed(time):
    available_digits = sorted(set(time))
    available_digits.remove(':')

    hour_tens = int(time[0])
    hour_ones = int(time[1])
    minute_tens = int(time[3])
    minute_ones = int(time[4])

    while True:
        minute_ones = find_next_greater(minute_ones, available_digits, 9)

        if minute_ones is None:
            minute_ones = int(available_digits[0])
            minute_tens = find_next_greater(minute_tens, available_digits, 5)

            if minute_tens is None:
                minute_tens = int(available_digits[0])
                hour_ones = find_next_greater(hour_ones, available_digits, 9 if hour_tens < 2 else 3)

                if hour_ones is None:
                    hour_ones = int(available_digits[0])
                    hour_tens = find_next_greater(hour_tens, available_digits, 2)

                    if hour_tens is None:
                        # We need to start over from the smallest possible time
                        hour_tens = int(available_digits[0])
                        hour_ones = int(available_digits[0])
                       minute_tens = int(available_digits[0])
                        minute_ones = int(available_digits[0])
       
        hour = hour_tens * 10 + hour_ones
        if hour < 24:
            #Ensure this is a valid hour before returning.
            break
    return str(hour_tens) + str(hour_ones) + ':' + str(minute_tens) + str(minute_ones)

def find_next_greater(current_digit, available_digits, limit):
    for digit in available_digits:
        digit = int(digit)
        if digit > current_digit and digit <= limit:
            return digit
    return None

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input time string	Return null or throw IllegalArgumentException, as a valid time cannot be derived.
Input time string is invalid format (e.g., missing colon, incorrect length)	Throw IllegalArgumentException as parsing will fail and the time digits cannot be extracted.
All digits in the input time are the same (e.g., '11:11')	The algorithm must correctly find the next valid time using this single available digit by wrapping around when needed.
The provided digits cannot form a valid time (e.g., digits are 4, 5, 6, 7)	The algorithm should wrap around to the smallest possible valid time that can be formed with available digits, like '00:00' if 0 is available.
Input time is '23:59'	The next closest time must correctly wrap around to the earliest possible time composed of available digits.
Integer overflow when calculating possible next times	The algorithm should use string manipulation to avoid integer overflow when generating and comparing times.
Time contains non-digit characters	Throw an exception, or filter down to valid digit characters and continue.
Only one unique digit is provided, and that digit can only be used in one location, creating an impossible scenario for some time components	Algorithm should handle constraints such as the tens place for hours only having a digit from 0-2 available within the provided digits.