# LeetCode 949: Largest Time for Given Digits

## Problem Restatement

We are given an array `arr` containing exactly four digits.

We need to use each digit exactly once to form a valid 24-hour time in this format:

```text
HH:MM
```

The hour must be between:

```text
00 and 23
```

The minute must be between:

```text
00 and 59
```

Return the latest valid time that can be made.

If no valid time can be made, return an empty string. The official statement defines the same requirement: use all four digits exactly once and return the largest valid 24-hour time, or `""` if impossible.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `arr` with exactly four digits |
| Output | Latest valid time as `"HH:MM"` |
| Hour range | `00` to `23` |
| Minute range | `00` to `59` |
| Failure case | Return `""` |
| Digit rule | Use every digit exactly once |

Function shape:

```python
class Solution:
    def largestTimeFromDigits(self, arr: list[int]) -> str:
        ...
```

## Examples

Example 1:

```python
arr = [1, 2, 3, 4]
```

A valid latest time is:

```text
23:41
```

So the answer is:

```python
"23:41"
```

Example 2:

```python
arr = [5, 5, 5, 5]
```

No valid hour can be formed, because every possible hour starts with `5`.

So the answer is:

```python
""
```

Example 3:

```python
arr = [0, 0, 0, 0]
```

The only possible time is:

```python
"00:00"
```

So the answer is:

```python
"00:00"
```

## First Thought

There are only four digits.

The number of possible arrangements is:

```text
4! = 24
```

That is very small.

So we can simply try every permutation, check whether it forms a valid time, and keep the largest one.

## Key Insight

A time string has this structure:

```text
h1 h2 : m1 m2
```

For a permutation `(a, b, c, d)`:

```python
hour = 10 * a + b
minute = 10 * c + d
```

It is valid if:

```python
hour < 24
minute < 60
```

Among valid times, a larger `hour` is better.

If hours are equal, a larger `minute` is better.

So we can compare total minutes since midnight:

```python
hour * 60 + minute
```

## Algorithm

Initialize:

```python
best_minutes = -1
best_time = ""
```

For every permutation of `arr`:

1. Compute `hour`.
2. Compute `minute`.
3. Check whether the time is valid.
4. Convert it to total minutes.
5. If it is larger than the best seen so far, update the answer.

Return `best_time`.

## Walkthrough

Use:

```python
arr = [1, 2, 3, 4]
```

Some permutations:

| Digits | Time | Valid? |
|---|---|---|
| `[1, 2, 3, 4]` | `12:34` | Yes |
| `[2, 3, 4, 1]` | `23:41` | Yes |
| `[2, 4, 1, 3]` | `24:13` | No |
| `[3, 4, 1, 2]` | `34:12` | No |

Among all valid times, the latest is:

```python
"23:41"
```

## Correctness

The algorithm checks every possible ordering of the four digits.

Every valid time using the four digits exactly once corresponds to one of these permutations.

For each permutation, the algorithm computes the corresponding hour and minute and accepts it only if the hour is less than `24` and the minute is less than `60`. Therefore, every accepted candidate is a valid 24-hour time.

The algorithm compares valid candidates by total minutes since midnight. This ordering is exactly the chronological ordering of times within one day.

Since every possible valid time is considered and the algorithm keeps the largest one, the returned string is the latest valid time.

If no permutation forms a valid time, no valid answer exists, and the algorithm correctly returns an empty string.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(1)` | There are only `24` permutations |
| Space | `O(1)` | Only a few variables are stored |

Even though we use permutations, the input size is fixed at four digits.

## Implementation

```python
from itertools import permutations

class Solution:
    def largestTimeFromDigits(self, arr: list[int]) -> str:
        best_minutes = -1
        best_time = ""

        for a, b, c, d in permutations(arr):
            hour = 10 * a + b
            minute = 10 * c + d

            if hour >= 24 or minute >= 60:
                continue

            total = hour * 60 + minute

            if total > best_minutes:
                best_minutes = total
                best_time = f"{hour:02d}:{minute:02d}"

        return best_time
```

## Code Explanation

We generate every ordering of the four digits:

```python
for a, b, c, d in permutations(arr):
```

The first two digits form the hour:

```python
hour = 10 * a + b
```

The last two digits form the minute:

```python
minute = 10 * c + d
```

Invalid times are skipped:

```python
if hour >= 24 or minute >= 60:
    continue
```

For valid times, compare by total minutes:

```python
total = hour * 60 + minute
```

When a better time is found, format it with two digits for hour and minute:

```python
best_time = f"{hour:02d}:{minute:02d}"
```

This correctly produces values like:

```text
00:00
01:09
23:41
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.largestTimeFromDigits([1, 2, 3, 4]) == "23:41"
    assert s.largestTimeFromDigits([5, 5, 5, 5]) == ""
    assert s.largestTimeFromDigits([0, 0, 0, 0]) == "00:00"
    assert s.largestTimeFromDigits([0, 0, 1, 0]) == "10:00"
    assert s.largestTimeFromDigits([2, 0, 6, 6]) == "06:26"
    assert s.largestTimeFromDigits([2, 3, 5, 9]) == "23:59"

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[1,2,3,4]` | Standard valid case |
| `[5,5,5,5]` | No valid hour |
| `[0,0,0,0]` | All zeros |
| `[0,0,1,0]` | Requires leading zero handling |
| `[2,0,6,6]` | Best hour is not `20` because minute constraints matter |
| `[2,3,5,9]` | Latest possible time |