Valid 24-Hour Times from Digits

Overview

The goal of this problem is to find how many unique "HH:MM" combinations can be formed using four given digits ${A, B, C, D}$. Since we are only dealing with four digits, the total number of permutations is very small ($4! = 24$).

The constraints for a valid 24-hour time are:

• The hours ($HH$) must be between $00$ and $23$.
• The minutes ($MM$) must be between $00$ and $59$.

The primary challenge is ensuring we count each unique time only once, even if the input digits contain duplicates (e.g., ${2, 2, 3, 3}$).

Brute Force

The brute force approach involves generating every possible permutation of the four input digits. For each permutation, we treat the first two digits as the hour and the last two as the minute. We then validate if the hour is $< 24$ and the minute is $< 60$. To handle duplicate digits and avoid double-counting the same time string, we can store valid results in a set.

import itertools

def countValidTimes(A: int, B: int, C: int, D: int) -> int:
    digits = [A, B, C, D]
    valid_times = set()
    
    # Generate all permutations of the 4 digits
    for p in itertools.permutations(digits):
        hour = p[0] * 10 + p[1]
        minute = p[2] * 10 + p[3]
        
        # Check if the combination forms a valid 24-hour time
        if 0 <= hour <= 23 and 0 <= minute <= 59:
            valid_times.add((hour, minute))
            
    return len(valid_times)

Time complexity: O(1) — There are always exactly $4! = 24$ permutations to check regardless of the input values. Space complexity: O(1) — The set will store at most 24 unique time pairs.

Optimal / Best Approach

The optimal approach is essentially the same as the brute force because the input size is fixed at 4. However, we can implement it without external libraries by using nested loops or a simple backtracking recursive function to pick digits. This avoids the overhead of itertools while maintaining clarity.

We iterate through all possible assignments of the digits to the positions $H_1, H_2, M_1, M_2$. To handle duplicates correctly without a set, we can sort the input digits initially and ensure we only process unique permutations, or stick to the set for simplicity as it is highly efficient for this scale.

def countValidTimes(A: int, B: int, C: int, D: int) -> int:
    nums = [A, B, C, D]
    count = 0
    seen_times = set()
    
    # Indices i, j, k, l represent the positions in the time HH:MM
    for i in range(4):
        for j in range(4):
            if j == i: continue
            for k in range(4):
                if k == i or k == j: continue
                for l in range(4):
                    if l == i or l == j or l == k: continue
                    
                    hour = nums[i] * 10 + nums[j]
                    minute = nums[k] * 10 + nums[l]
                    
                    if 0 <= hour <= 23 and 0 <= minute <= 59:
                        time_tuple = (hour, minute)
                        if time_tuple not in seen_times:
                            count += 1
                            seen_times.add(time_tuple)
                            
    return count

Time complexity: O(1) — The algorithm performs a constant number of operations ($4 \times 3 \times 2 \times 1 = 24$ iterations). Space complexity: O(1) — We store a constant number of valid times in a set (maximum 24).

Why this works

1. Permutations vs. Combinations: We need permutations because the order matters (e.g., 12:38 is different from 21:38).
2. Handling Duplicates: If the input is [1, 2, 1, 2], the digit at index 0 and index 2 are both 1. If we swap them, we get the same time. The set ensures that "12:12" is only counted once even though it can be formed by different index combinations.
3. Validation Logic: - hour < 24 automatically covers the rules for the first digit (must be 0, 1, or 2) and the second digit (if first is 2, second must be $\le 3$).
   • minute < 60 ensures the first minute digit is $\le 5$.

Fast