Largest Time for Given Digits: Permutation and Validation

You are given an array of four digits (each between 0 and 9). Your task is to find the largest 24-hour time that can be formed using each digit exactly once. If no valid time exists, return an empty string. This is LeetCode 949: Largest Time for Given Digits.

The time format is "HH:MM", where HH ranges from 00 to 23 and MM ranges from 00 to 59. Every digit must be used exactly once.

The problem

Given four digits in an array arr, return the largest 24-hour time that can be displayed. If no valid time is possible, return "".

For example, given [1, 2, 3, 4], the answer is "23:41". Given [5, 5, 5, 5], no valid time exists, so the answer is "".

Why this problem matters

This problem is a clean exercise in enumeration and validation. It asks you to generate all arrangements of a small set and filter by a constraint. That "generate, then validate" pattern shows up constantly in interview problems, from sudoku solvers to combination sums to scheduling.

Because the input is always exactly four digits, the total number of permutations is just 4! = 24. That tiny search space means brute force is not just acceptable, it is the intended approach. The real challenge is correctly validating each permutation against the 24-hour clock rules, which tests your attention to edge cases.

The brute force approach

Since there are only 24 permutations of four digits, you can enumerate all of them, check whether each forms a valid time, and track the maximum.

from itertools import permutations

def largest_time_brute(arr):
    best = -1
    for p in permutations(arr):
        hours = p[0] * 10 + p[1]
        minutes = p[2] * 10 + p[3]
        if hours < 24 and minutes < 60:
            total = hours * 60 + minutes
            if total > best:
                best = total
    if best == -1:
        return ""
    return f"{best // 60:02d}:{best % 60:02d}"

This is already efficient enough. With only 24 iterations and O(1) work per iteration, there is no performance problem to solve. The brute force approach is the clean solution for this problem.

The key insight

Four digits produce only 24 permutations. You do not need any clever pruning, backtracking, or optimization. Just enumerate, validate, and track the best. The constraint space is small enough that brute force runs in constant time.

The validation itself is the interesting part. A permutation [a, b, c, d] forms the time ab:cd. For this to be valid, 10*a + b must be less than 24, and 10*c + d must be less than 60. Converting to total minutes (hours * 60 + minutes) makes comparison easy.

Walking through it step by step

Let's trace through the input [1, 2, 3, 4]. We generate permutations, check validity, and update our best time whenever we find a larger valid one.

After checking all 24 permutations, the largest valid time is "23:41". Many permutations are valid, but several (like 43:21 or 34:12) fail the hour constraint. The algorithm considers them all and picks the winner.

The clean solution

from itertools import permutations

def largestTimeFromFourDigits(arr):
    best = -1
    for h1, h2, m1, m2 in permutations(arr):
        hours = h1 * 10 + h2
        minutes = m1 * 10 + m2
        if hours < 24 and minutes < 60:
            total = hours * 60 + minutes
            best = max(best, total)
    if best == -1:
        return ""
    return f"{best // 60:02d}:{best % 60:02d}"

The destructuring for h1, h2, m1, m2 in permutations(arr) makes the mapping from digits to time slots crystal clear. Each permutation assigns the four digits to the two hour positions and two minute positions. The validation is two simple comparisons. Converting to total minutes for tracking the maximum avoids messy string comparisons.

If no valid time was found, best stays at -1 and we return the empty string. Otherwise, we convert back from total minutes to the "HH:MM" format using integer division and modulo.

Complexity analysis

The input is always four digits, so the number of permutations is fixed at 4! = 24. Each permutation takes O(1) to validate. The total work is constant regardless of the digit values. Space is also O(1) since we only store the current best and a few temporary variables.

Building blocks

1. Exhaustive permutation enumeration

When the search space is small and fixed, generating every permutation and checking each one is a clean and reliable strategy. This same pattern appears in problems like Permutations and Permutations II, though those problems ask you to build the enumeration yourself rather than using a library function. The core idea is the same: systematically visit every arrangement.

2. Constraint validation

After generating a candidate, you validate it against the problem's rules. Here, the constraints are the 24-hour clock bounds. In other problems, the constraints might be sudoku rules, graph connectivity, or sum targets. The pattern is always the same: generate a candidate, check if it satisfies all constraints, and keep or discard it.

Edge cases

• No valid time exists. Input [5, 5, 5, 5] has no permutation where hours are less than 24 and minutes are less than 60. Return "".
• Midnight. Input [0, 0, 0, 0] produces "00:00", which is a valid time.
• All digits the same but valid. Input [1, 1, 1, 1] produces "11:11".
• Only one valid permutation. Input [2, 3, 5, 9] has very few valid times. The algorithm checks all 24 and finds the best.
• Digits that could form 23:59. Input [2, 3, 5, 9] can form "23:59", the largest possible 24-hour time.
• Duplicate digits. Input [1, 1, 2, 2] produces duplicate permutations, but since we track the max, duplicates do not cause problems. They just result in redundant checks.

Common mistakes

1. Forgetting that hours go up to 23, not 24. A time like "24:00" is invalid. The condition must be hours < 24, not hours <= 24.

2. Forgetting that minutes go up to 59, not 60. Similarly, "12:60" is invalid. Use minutes < 60.

3. Returning "00:00" instead of "" when no valid time exists. If the input is [5, 5, 5, 5], the answer is an empty string, not midnight. Make sure your default case returns "".

4. Using string comparison instead of numeric comparison. Comparing times as strings can work if formatted correctly, but converting to total minutes is safer and avoids subtle bugs with zero-padding.

5. Not considering all 24 permutations. Some people try to be clever with greedy digit placement (put the largest valid digit in H1, then H2, etc.). This greedy approach does not always produce the correct answer because choosing a slightly smaller hour can unlock a much larger minute value.

From understanding to recall

This problem tests a very specific skill: recognizing that a tiny search space means you should enumerate rather than optimize. The instinct to look for a clever algorithm is strong, but here the clever move is to not be clever.

When you review this problem, ask yourself: how many permutations are there? If the answer is small (say, under a few thousand), exhaustive search is almost always the right approach. Practice writing the permutation-and-validate loop from memory until it feels automatic.

The validation logic (hours less than 24, minutes less than 60) is the part most likely to trip you up under pressure. Drill it until the bounds are second nature.

Related posts

• Permutations - Building permutation enumeration from scratch using backtracking
• Next Permutation - Generating the next lexicographic permutation in-place
• Permutations II - Handling duplicate elements in permutation generation

CodeBricks breaks the largest time for given digits problem into its permutation enumeration and constraint validation building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a small-search-space enumeration question shows up in your interview, you do not think about it. You just write it.