Number of Valid Clock Times - Solution & Explanation
Problem Statement
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:
timeis a valid string of length5in 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 from0to9.
Approach Overview
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.
Approach 1: Brute Force Enumeration
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.
Complexity
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.
Approach 2: Character-Specific Enumeration
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.
Complexity
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.
Approach 3: Enumeration
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).
Approach 4: Optimized Enumeration
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).
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
2437. Number of Valid Clock Times (Leetcode Easy) • Programming Live with Larry • 686 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Valid Clock Times easy or hard?
Number of Valid Clock Times Python/Java solution
How to solve Number of Valid Clock Times in O(1)?
What is the best approach for Number of Valid Clock Times?
Is Number of Valid Clock Times asked at Google/Amazon/Meta?
What data structure is used in Number of Valid Clock Times?
What is the time complexity of Number of Valid Clock Times?
Ready to solve this problem?
Practice Number of Valid Clock Times with our built-in code editor and test cases.
Practice on FleetCode