Number of Valid Clock Times

EASY

Description

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

Checkout 2 different approaches to solve Number of Valid Clock Times. Click on different approaches to view the approach and algorithm in detail.

Brute-Force by Iterating All Valid Times

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.

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 Analysis

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

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Number of Valid Clock Times. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Number of Valid Clock Times

Patterns:

Enumeration

Data Structures:

String