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"'?' and need to be replaced with digits from 0 to 9.Problem Overview: You receive a time string in the format hh:mm where some digits may be replaced with ?. Each ? can represent any digit. The task is to count how many valid 24‑hour clock times (00:00–23:59) can be formed by replacing the unknown characters.
Approach 1: Brute Force Enumeration (O(1440) time, O(1) space)
The simplest strategy is to enumerate every possible valid time in a 24‑hour day. There are only 24 * 60 = 1440 combinations. Iterate through all hours from 00 to 23 and minutes from 00 to 59, convert each candidate into a string, and compare it with the input pattern. A candidate is valid if every non‑? character in the input matches the corresponding digit in the generated time. This approach uses straightforward enumeration and simple string comparison. Since the search space is fixed (1440), the runtime is effectively constant and trivial to implement in any language.
Approach 2: Character-Specific Enumeration (O(1) time, O(1) space)
Instead of checking every full time, compute the number of valid options for the hour and minute positions independently. For minutes, the first digit can be 0–5 and the second 0–9, adjusted based on whether the input contains a fixed digit or ?. Hours require slightly more logic because the valid range is 00–23. If both hour digits are ?, there are 24 possibilities. If only the first digit is ?, the second digit determines whether the first can be 0–2 or only 0–1. If only the second digit is ?, the allowed range depends on whether the first digit is 2 (then 0–3) or 0–1 (then 0–9). Multiply the number of valid hour combinations by the number of valid minute combinations. This direct counting method leverages constraints of the clock format and avoids scanning all possibilities.
Recommended for interviews: Start with the brute force enumeration to show you understand the valid time space (1440 possibilities). Then mention the character‑specific counting approach, which computes the answer in constant time by analyzing each digit position. Interviewers typically expect the optimized counting logic because it demonstrates strong reasoning about constraints and efficient enumeration without unnecessary iteration.
In this approach, we iterate over all possible valid hours and minutes, checking if a given configuration of the time string with '?' replaced can form a valid time. The constraints allow us to simply enumerate the values and check against the string.
This Python solution iterates through all potential hours (0 through 23) and minutes (0 through 59). For each hour-minute combination, it formats them into strings 'hh' and 'mm'. It then checks if each character matches the corresponding character in the given time string or if the character is '?', which can match any digit. If all positions match or are '?', this configuration of time is considered valid, and the count is incremented.
The time complexity is O(1) since there are at most 24*60 = 1440 iterations. The space complexity is O(1) as we use only a few variables to store numbers and strings.
This approach simplifies the task by considering each position of '?' in the string individually, providing specific potential values given constraints (e.g., for 'hh', values depend on `time[0]`).
The Python optimized solution calculates the number of valid replacements by checking each character in 'time'. Depending on whether a character is '?', it multiplies the total possible number of ways by the valid number of digits appropriate for that character.
Time Complexity: O(1), due to the constant number of checks and multiplicative operations. Space Complexity: O(1) as only a few integer calculations are involved.
We can directly enumerate all times from 00:00 to 23:59, then judge whether each time is valid, if so, increment the answer.
After the enumeration ends, return the answer.
The time complexity is O(24 times 60), and the space complexity is O(1).
We can separately enumerate hours and minutes, count how many hours and minutes meet the condition, and then multiply them together.
The time complexity is O(24 + 60), and the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Brute Force Enumeration | The time complexity is O(1) since there are at most 24*60 = 1440 iterations. The space complexity is O(1) as we use only a few variables to store numbers and strings. |
| Character-Specific Enumeration | Time Complexity: O(1), due to the constant number of checks and multiplicative operations. Space Complexity: O(1) as only a few integer calculations are involved. |
| Enumeration | — |
| Optimized Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(1440) | O(1) | When you want the simplest implementation or to quickly validate the pattern against all valid times |
| Character-Specific Enumeration | O(1) | O(1) | Preferred solution in interviews; directly counts valid combinations using clock constraints |
2437. Number of Valid Clock Times (Leetcode Easy) • Programming Live with Larry • 673 views views
Watch 9 more video solutions →Practice Number of Valid Clock Times with our built-in code editor and test cases.
Practice on FleetCode