Number of Valid Clock Times

Easy

Asked by:

27 views

Topics:

Strings

You are given a string of length 5 called time, representing the current time on a digital clock in the format "hh:mm". The earliest possible time is "00:00" and the latest possible time is "23:59".

In the string time, the digits represented by the ? symbol are unknown, and must be replaced with a digit from 0 to 9.

Return an integer answer, the number of valid clock times that can be created by replacing every ? with a digit from 0 to 9.

Example 1:

Input: time = "?5:00"
Output: 2
Explanation: We can replace the ? with either a 0 or 1, producing "05:00" or "15:00". Note that we cannot replace it with a 2, since the time "25:00" is invalid. In total, we have two choices.

Example 2:

Input: time = "0?:0?"
Output: 100
Explanation: Each ? can be replaced by any digit from 0 to 9, so we have 100 total choices.

Example 3:

Input: time = "??:??"
Output: 1440
Explanation: There are 24 possible choices for the hours, and 60 possible choices for the minutes. In total, we have 24 * 60 = 1440 choices.

Constraints:

time is a valid string of length 5 in the format "hh:mm".
"00" <= hh <= "23"
"00" <= mm <= "59"
Some of the digits might be replaced with '?' and need to be replaced with digits from 0 to 9.

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:

The input time is a string of length 5 in the format 'HH:MM'. Can `HH` and `MM` contain question marks ('?')?
If some digits are unknown (represented by '?'), what is the valid range of possible values for each digit (e.g., is '??:??' allowed as input)?
Is the input always a valid string of length 5, or should I validate the input format before attempting to generate valid times?
If no valid time can be generated from the input, what should I return? (e.g., -1, 0, null)
Are there any leading zeros I need to handle specifically (e.g., should I treat '01' and '1' as the same hour value when generating times)?

Brute Force Solution

Approach

The brute force approach to finding the number of valid clock times involves checking every possible time combination. We treat each question mark in the input as a digit we need to figure out. We will systematically explore all digit possibilities for each question mark and count the valid times.

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

Consider all the possibilities for the first digit of the hours.
For each possibility of the first digit, consider all possibilities for the second digit of the hours.
Check if the combination of the first and second hour digits represents a valid hour (between 0 and 23).
If the hours are valid, consider all possibilities for the first digit of the minutes.
For each possibility of the first minute digit, consider all possibilities for the second digit of the minutes.
Check if the combination of the first and second minute digits represents a valid minute (between 0 and 59).
If both the hours and minutes are valid, increment a counter that keeps track of the total number of valid times.
Once we have explored all possibilities for each digit, the counter will contain the total number of valid clock times.

Code Implementation

def number_of_valid_clock_times(clock_time):
    valid_time_count = 0

    # Iterate through all possible values for the first digit of the hour
    for first_hour_digit in range(10) if clock_time[0] == '?' else [int(clock_time[0])]:
        # Iterate through all possible values for the second digit of the hour
        for second_hour_digit in range(10) if clock_time[1] == '?' else [int(clock_time[1])]:

            # Construct the hour from the digits and check if it's valid
            hour = first_hour_digit * 10 + second_hour_digit
            if 0 <= hour <= 23:

                # Iterate through all possible values for the first digit of the minute
                for first_minute_digit in range(6) if clock_time[3] == '?' else [int(clock_time[3])]:
                    # Iterate through all possible values for the second digit of the minute
                    for second_minute_digit in range(10) if clock_time[4] == '?' else [int(clock_time[4])]:

                        # Construct the minute from the digits
                        minute = first_minute_digit * 10 + second_minute_digit

                        # Check if the constructed minute is valid                       if 0 <= minute <= 59:
                            valid_time_count += 1

    return valid_time_count

Big(O) Analysis

Time Complexity

O(1) – The problem explores all possible combinations of digits for the hours and minutes based on the question marks present in the input string, which has a fixed size. There are at most four question marks. Even in the worst-case scenario where all characters are question marks, the maximum number of combinations checked is limited (24 possibilities for hours and 60 for minutes giving 24*60=1440). Since the input size is fixed and the number of operations performed is bounded by a constant, the time complexity is O(1). It does not scale with an increasing input size.

Space Complexity

O(1) – The provided algorithm uses a brute-force approach that explores digit possibilities directly. It does not create any auxiliary data structures like arrays, lists, or hash maps to store intermediate results or track visited states. The space used is limited to a few integer variables to hold the counts and loop indices, which is independent of the input string's length. Therefore, the space complexity is constant.

Optimal Solution

Approach

We are trying to find how many valid times we can make given a clock time with some question marks. Instead of checking all possibilities, we'll treat each part of the time separately and figure out how many valid options exist for that part, then combine the results.

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

Look at the first two spots of the time (the hours). If there are question marks, figure out how many valid numbers can go there (00 to 23). Remember to handle different cases based on whether there are one or two question marks, or specific digits already present.
Do the same thing for the last two spots of the time (the minutes). The possible values are 00 to 59, so count how many numbers fit given any question marks.
If there's a colon in the middle, we don't need to worry about it. It's just there to separate the hours and minutes.
Multiply the number of valid hours by the number of valid minutes. The result is the total number of valid clock times you can make.

Code Implementation

def number_of_valid_clock_times(time):
    hours = time[0:2]
    minutes = time[3:5]

    def count_valid_hours(hour_string):
        if hour_string == "??":
            return 24
        elif hour_string[0] == "?":
            # Need to check based on the second digit.
            if hour_string[1] <= '3':
                return 3
            else:
                return 2
        elif hour_string[1] == "?":
            # Need to check based on the first digit.
            if hour_string[0] == '0' or hour_string[0] == '1':
                return 10
            else:
                return 4
        else:
            hour_value = int(hour_string)
            if 0 <= hour_value <= 23:
                return 1
            else:
                return 0

    def count_valid_minutes(minute_string):
        if minute_string == "??":
            return 60
        elif minute_string[0] == "?":
            return 6
        elif minute_string[1] == "?":
            # Any digit is valid if the first digit is 0-5
            return 10
        else:
            minute_value = int(minute_string)
            if 0 <= minute_value <= 59:
                return 1
            else:
                return 0

    valid_hours = count_valid_hours(hours)
    valid_minutes = count_valid_minutes(minutes)

    # The total count is product of valid hours and minutes.
    return valid_hours * valid_minutes

Big(O) Analysis

Time Complexity

O(1) – The algorithm processes a fixed-size input string representing the clock time, which is always 5 characters long (HH:MM). The steps involve examining the first two characters (hours) and the last two characters (minutes) independently. The number of operations performed on each part (hours and minutes) is constant, regardless of the actual digits or question marks present. Therefore, the overall time complexity is O(1) because it performs a fixed number of operations.

Space Complexity

O(1) – The provided explanation focuses on calculating valid combinations for hours and minutes independently without using any auxiliary data structures that scale with the input size (the length of the time string). It performs constant-time operations on the input string to count possibilities. Therefore, the algorithm uses a constant amount of extra space, regardless of the length of the input string (N), because it doesn't create any lists, maps, or call stacks dependent on N.

Edge Cases

Case	How to Handle
Input string is null or empty	Return 1 since '??:??' is a valid initial state representing all possible times.
Input string contains characters other than '?' and digits	Throw an IllegalArgumentException or return an error code indicating invalid input.
Input string length is not 5	Throw an IllegalArgumentException or return an error code as the time format should be HH:MM.
First digit '?' and second digit '?'	Multiply the possible values (2 * 10 = 20) if the first two digits are both '?'.
First digit is '2' and second digit is '?'	Second digit can range from 0-3 if the first is a 2 else it ranges from 0-9 if the first is a 0 or a 1, or '?'
Fourth digit is '?'	Fourth digit can range from 0-5.
Third character is not ':'	Throw an IllegalArgumentException as the format HH:MM is mandatory.
Combination of '?' values that results in edge case around 23:59	Account for limitations on what values each question mark can resolve to based on the adjacent characters.

Input string is null or empty

How to Handle:

Return 1 since '??:??' is a valid initial state representing all possible times.

Input string contains characters other than '?' and digits

How to Handle:

Throw an IllegalArgumentException or return an error code indicating invalid input.

Input string length is not 5

How to Handle:

Throw an IllegalArgumentException or return an error code as the time format should be HH:MM.

First digit '?' and second digit '?'

How to Handle:

Multiply the possible values (2 * 10 = 20) if the first two digits are both '?'.

First digit is '2' and second digit is '?'

How to Handle:

Second digit can range from 0-3 if the first is a 2 else it ranges from 0-9 if the first is a 0 or a 1, or '?'

Fourth digit is '?'

How to Handle:

Fourth digit can range from 0-5.

Third character is not ':'

How to Handle:

Throw an IllegalArgumentException as the format HH:MM is mandatory.

Combination of '?' values that results in edge case around 23:59

How to Handle:

Account for limitations on what values each question mark can resolve to based on the adjacent characters.