Count valid 24-hour times from four digits

Clarify first. You get four digits, each from 0 to 9. Arrange all four as HH:MM on a 24-hour clock, using each given digit exactly once. Count the distinct valid times. Ask these questions before you code:

• Duplicates. If the digits repeat (for example 2, 2, 3, 3), two arrangements can show the same time. Count each distinct time once. This is the detail most candidates miss.
• Range. Hours are 00 to 23. Minutes are 00 to 59. Leading zeros count as digits, so 0, 0, 0, 0 gives 00:00.
• Output. A count, not the list. (Returning the sorted list is a common follow-up.)

Brute force: try every arrangement. Four digits have 4! = 24 orderings. For each ordering (a, b, c, d), the hour is 10a + b and the minute is 10c + d. Keep it if hour < 24 and minute < 60. Put the (hour, minute) pairs in a set so repeated digits do not double-count. The answer is the size of the set.

This is already optimal for the stated problem: 24 checks is constant work. The interviewer wants to see that you handle duplicates correctly and write clean code, not a clever algorithm.

Alternative: walk the clock. There are only 24 * 60 = 1440 times. For each one, build its four digits and compare their multiset with the input (compare sorted lists, or Counters). Each time is checked once, so duplicates take care of themselves. This is also constant work. It scales better when the number of digits or arrangements grows faster than the number of clock values (for example 6 digits with seconds: 720 permutations against 86400 times, so here permutations still win; but with digit reuse allowed, walking the clock is the natural method).

Invariant. A time is counted exactly when its four digits, as a multiset, equal the input multiset. Both methods enforce that: the permutation method by construction plus the set, the clock walk by direct comparison.

Pruning, if asked to be smarter. Fix the hour first. Choose an ordered pair of positions for HH (12 pairs), check HH <= 23, then the remaining two digits give at most two minute values. That is at most 24 checks with early exits, and it is the shape that extends to "find the latest time" (LeetCode 949).

from __future__ import annotations

from collections import Counter
from itertools import permutations


def count_valid_times(a: int, b: int, c: int, d: int) -> int:
    """Count distinct 24-hour times HH:MM that use each digit exactly once."""
    digits = (a, b, c, d)
    if any(not 0 <= x <= 9 for x in digits):
        raise ValueError("each input must be a single digit 0-9")

    seen: set[tuple[int, int]] = set()
    for h1, h2, m1, m2 in permutations(digits):
        hour = h1 * 10 + h2
        minute = m1 * 10 + m2
        if hour < 24 and minute < 60:
            seen.add((hour, minute))
    return len(seen)


def count_valid_times_by_clock(a: int, b: int, c: int, d: int) -> int:
    """Same answer by scanning all 1440 times and matching digit multisets."""
    target = Counter((a, b, c, d))
    count = 0
    for hour in range(24):
        for minute in range(60):
            shown = (hour // 10, hour % 10, minute // 10, minute % 10)
            if Counter(shown) == target:
                count += 1
    return count


def list_valid_times(a: int, b: int, c: int, d: int) -> list[str]:
    """Follow-up: the distinct valid times as sorted 'HH:MM' strings."""
    times: set[str] = set()
    for h1, h2, m1, m2 in permutations((a, b, c, d)):
        hour, minute = h1 * 10 + h2, m1 * 10 + m2
        if hour < 24 and minute < 60:
            times.add(f"{hour:02d}:{minute:02d}")
    return sorted(times)


if __name__ == "__main__":
    assert count_valid_times(1, 8, 3, 2) == 6
    assert list_valid_times(1, 8, 3, 2) == [
        "12:38", "13:28", "18:23", "18:32", "21:38", "23:18",
    ]
    assert count_valid_times(2, 3, 3, 2) == 3
    assert count_valid_times(6, 2, 4, 7) == 0
    assert count_valid_times(0, 0, 0, 0) == 1
    assert count_valid_times(1, 1, 1, 1) == 1
    assert count_valid_times(9, 9, 9, 9) == 0
    assert count_valid_times(0, 1, 2, 3) == 18
    assert count_valid_times(2, 4, 0, 0) == 8
    for digits in [(a, b, c, d) for a in range(10) for b in range(10)
                   for c in range(10) for d in range(10)]:
        assert count_valid_times(*digits) == count_valid_times_by_clock(*digits)
    print("all tests passed")

• count_valid_times: 4! = 24 permutations, each checked in O(1). Time O(1), space O(1) (the set holds at most 24 pairs). For n digits in general it is O(n!) time and space.
• count_valid_times_by_clock: 1440 times, each compared in O(1). Time O(1), space O(1). In general it is O(number of clock values).
• list_valid_times: O(1) time and space, plus sorting at most 24 strings.

• 1, 8, 3, 2 -> 6 (12:38, 13:28, 18:23, 18:32, 21:38, 23:18).
• 2, 3, 3, 2 -> 3 (22:33, 23:23, 23:32). Repeated digits; a naive count of permutations gives 12.
• 6, 2, 4, 7 -> 0. Every hour that starts with 2 is 24 or more, and there is no 0 or 1.
• 0, 0, 0, 0 -> 1 (00:00).
• 1, 1, 1, 1 -> 1 (11:11).
• 9, 9, 9, 9 -> 0.
• 0, 1, 2, 3 -> 18. Of the 12 ordered hour pairs, the 9 that start with 0, 1 or 2 are valid hours and the 3 that start with 3 are not. The two digits left over are at most 3, so both minute orders are valid. That is 9 hours times 2 = 18.
• 2, 4, 0, 0 -> 8 (00:24, 00:42, 02:04, 02:40, 04:02, 04:20, 20:04, 20:40). Checks the 24 boundary: 24:00 is not valid.
• Exhaustive check: both methods agree on all 10,000 digit tuples.

1. Return the latest (or earliest) valid time. This is LeetCode 949. Track the maximum (hour, minute) instead of a set, or try hours from 23 down and minutes from 59 down and return the first match. Return "" when none exist.
2. 12-hour clock. Change the hour check to 1 <= hour <= 12 (or 0 <= hour <= 11, ask which). Decide whether AM and PM double the count; usually they do not, since the display is the same.
3. Add seconds (six digits, HH:MM:SS). Permutations become 6! = 720, still small. Add second < 60. Walking the clock is 86400 checks, so permutations are cheaper here. Use the hour-first pruning to cut work further.
4. Digits may be reused. Each slot can use any given digit any number of times. Now walk the clock and check that every shown digit is in the input set; or count per position: the number of allowed HH values times the number of allowed MM values (MM is independent of HH). That product form is O(1) with tiny loops.
5. Many queries. Precompute, for each sorted 4-digit multiset (715 of them), its count in one pass over the 1440 times. Each query becomes a dictionary lookup on the sorted tuple.

Mid-level (L4)

• Asks how to treat repeated digits, then dedupes with a set.
• Writes the permutation loop correctly: hour < 24, minute < 60, leading zeros allowed.
• Tests at least one duplicate case and one zero-result case.

Senior (L5)

• Offers both methods (permutations and clock walk) and explains why each counts duplicates correctly.
• States complexity as constant for the fixed problem and O(n!) versus O(clock values) in general.
• Handles follow-ups 1 to 3 quickly by changing only the validity check or the reduction.

Staff (L6+)

• Chooses the method by comparing the size of the arrangement space and the clock space, and says when each wins.
• Sees the precompute-by-multiset idea for many queries and the product form for digit reuse.
• Writes a cross-check (the exhaustive comparison of both methods) as the test strategy, not only hand-picked cases.