Scale Engineer

Number of Valid Clock Times

Easy
#2221Time: O(1), since the number of iterations is constant (24 * 60 = 1440). Each check inside the loop takes constant time.Space: O(1), as it only uses a few variables to store the counter and the formatted time strings.
Patterns
Enumeration
Data structures
String

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iterating through every possible valid time from 00:00 to 23:59 and checking if each time matches the given pattern. A counter is incremented for each match.

Algorithm

  • Initialize a counter count to 0.
  • Create a nested loop. The outer loop iterates through hours h from 0 to 23.
  • The inner loop iterates through minutes m from 0 to 59.
  • Inside the inner loop, format the current h and m into two-digit strings hh and mm (e.g., 5 becomes "05").
  • Check if the formatted time hh:mm matches the input time pattern.
  • A character-by-character comparison is performed. A position matches if the pattern has a '?' or if the characters are identical.
  • If the entire time string matches the pattern, increment count.
  • After the loops complete, return count.

Walkthrough

The core idea is to simulate a digital clock and check every minute of a 24-hour day. We can generate all 1440 possible valid time strings (from "00:00" to "23:59") and, for each one, compare it against the input time pattern.

A helper function can be used to determine if a generated time string matches the pattern. This function compares the two strings character by character. A match occurs at a specific position if the character in the pattern is a '?' or if it is identical to the character in the generated time string. If all positions match, the generated time is a valid possibility.

For example, if the input is "?5:00", we would iterate from h=0, m=0 upwards. When we reach h=5, m=0, we format it to "05:00". This matches the pattern. When we reach h=15, m=0, we format it to "15:00", which also matches. No other time will match, so the final count is 2.

class Solution {    public int countTime(String time) {        int count = 0;        // Iterate through all possible hours (0-23)        for (int h = 0; h < 24; h++) {            // Iterate through all possible minutes (0-59)            for (int m = 0; m < 60; m++) {                // Format hour and minute to two digits with leading zeros if necessary                String hourStr = String.format("%02d", h);                String minuteStr = String.format("%02d", m);                                // Check if the generated time matches the pattern                if (matches(time, hourStr, minuteStr)) {                    count++;                }            }        }        return count;    }     private boolean matches(String pattern, String hour, String minute) {        // Check hour part        if (pattern.charAt(0) != '?' && pattern.charAt(0) != hour.charAt(0)) {            return false;        }        if (pattern.charAt(1) != '?' && pattern.charAt(1) != hour.charAt(1)) {            return false;        }        // Check minute part        if (pattern.charAt(3) != '?' && pattern.charAt(3) != minute.charAt(0)) {            return false;        }        if (pattern.charAt(4) != '?' && pattern.charAt(4) != minute.charAt(1)) {            return false;        }        return true;    }}

Complexity

Time

O(1), since the number of iterations is constant (24 * 60 = 1440). Each check inside the loop takes constant time.

Space

O(1), as it only uses a few variables to store the counter and the formatted time strings.

Trade-offs

Pros

  • Simple to conceptualize and implement.

  • Guaranteed to be correct as it exhaustively checks all possibilities.

Cons

  • Performs a fixed but relatively large number of operations (1440 checks), which is less efficient than a direct calculation.

Solutions

class Solution {public  int countTime(String time) {    int ans = 0;    for (int h = 0; h < 24; ++h) {      for (int m = 0; m < 60; ++m) {        String s = String.format("%02d:%02d", h, m);        int ok = 1;        for (int i = 0; i < 5; ++i) {          if (s.charAt(i) != time.charAt(i) && time.charAt(i) != '?') {            ok = 0;            break;          }        }        ans += ok;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem