Watch 10 video solutions for Number of Valid Clock Times, a easy level problem involving String, Enumeration. This walkthrough by Programming Live with Larry has 673 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |