# LeetCode 681: Next Closest Time

## Problem Restatement

We are given a valid time string in the format:

```text
HH:MM
```

We need to form the next closest valid time by reusing only the digits that already appear in the input time.

Each digit may be reused any number of times.

For example, if the input is:

```python
time = "19:34"
```

then the available digits are:

```text
1, 9, 3, 4
```

We may use these digits repeatedly to form another valid time.

The answer is the next valid time after the given time. If no valid time exists later on the same day, we wrap around to the next day. The official examples include `"19:34" -> "19:39"` and `"23:59" -> "22:22"`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A valid time string `time` in `"HH:MM"` format |
| Output | The next closest valid time using only digits from `time` |
| Format | Output must also be `"HH:MM"` |
| Digit reuse | Allowed without limit |
| Time range | `"00:00"` through `"23:59"` |

Example function shape:

```python
def nextClosestTime(time: str) -> str:
    ...
```

## Examples

Example 1:

```python
time = "19:34"
```

Available digits:

```text
1, 9, 3, 4
```

The next valid time is:

```python
"19:39"
```

It occurs 5 minutes later.

`"19:33"` is valid using the same digits, but it is almost 24 hours later, so it is not the closest next time.

Example 2:

```python
time = "23:59"
```

Available digits:

```text
2, 3, 5, 9
```

There is no valid later time on the same day using only these digits.

So we wrap around to the next day.

The answer is:

```python
"22:22"
```

## First Thought: Generate All Times

There are only 24 hours and 60 minutes.

That means there are only:

```text
24 * 60 = 1440
```

possible times in one day.

A simple approach is to move forward minute by minute.

For each next minute:

1. Convert it to `"HH:MM"`.
2. Check whether every digit belongs to the input digit set.
3. Return the first valid time.

This is simple and reliable because there are only 1440 possible minutes.

## Key Insight

The problem asks for the next closest time, not the smallest numeric time.

So time should be treated cyclically.

After `"23:59"`, the next minute is `"00:00"`.

The easiest way to handle this is to convert the input time into minutes since midnight.

For example:

```python
"19:34" -> 19 * 60 + 34 = 1174
```

Then we try:

```text
1175, 1176, 1177, ...
```

modulo `1440`.

This naturally wraps around after midnight.

## Algorithm

1. Extract the allowed digits from the input time, ignoring the colon.
2. Convert the input time to minutes since midnight.
3. For `step` from `1` to `1440`:
   - Compute the candidate minute:
     ```python id="ojsv6a"
     candidate = (current + step) % 1440
     ```
   - Convert `candidate` back to `"HH:MM"`.
   - Check whether all digits in the candidate time are allowed.
   - If yes, return that candidate.

We start from `step = 1` because the answer must be after the current time, not equal to it.

## Walkthrough

Consider:

```python
time = "19:34"
```

Allowed digits:

```text
{'1', '9', '3', '4'}
```

Current minute:

```text
19 * 60 + 34 = 1174
```

Now try later minutes:

| Candidate | Time | Uses only allowed digits? |
|---:|---|---:|
| 1175 | `"19:35"` | No, digit `5` is not allowed |
| 1176 | `"19:36"` | No, digit `6` is not allowed |
| 1177 | `"19:37"` | No, digit `7` is not allowed |
| 1178 | `"19:38"` | No, digit `8` is not allowed |
| 1179 | `"19:39"` | Yes |

So the answer is:

```python
"19:39"
```

Now consider:

```python
time = "23:59"
```

Allowed digits:

```text
{'2', '3', '5', '9'}
```

The current time is minute `1439`.

After that, we wrap to the next day.

Many early times such as `"00:00"` and `"11:11"` are not allowed because they use digits not in the set.

The first valid time is:

```python
"22:22"
```

## Correctness

The algorithm checks candidate times in exact chronological order after the input time.

For `step = 1`, it checks the time one minute later.

For `step = 2`, it checks the time two minutes later.

This continues until `step = 1440`, which returns to the original time after one full day.

Because time repeats every 1440 minutes, every possible valid time appears exactly once in this search order.

For each candidate, the algorithm checks whether all digits in its `"HH:MM"` representation are from the original time. Therefore, every returned time satisfies the digit-reuse rule.

The first candidate that satisfies this rule is the closest valid time after the input time, because all earlier candidates were checked first and rejected.

Therefore, the algorithm returns the correct next closest time.

## Complexity

There are at most 1440 candidate times.

Each candidate has fixed length 5, and we check 4 digits.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(1)` | At most 1440 fixed candidates |
| Space | `O(1)` | The digit set has at most 4 digits |

If written in terms of a full day length `D = 1440`, the time complexity is `O(D)`. Since `D` is fixed, it is constant for this problem.

## Implementation

```python
class Solution:
    def nextClosestTime(self, time: str) -> str:
        allowed = set(time)
        allowed.remove(":")

        hour = int(time[:2])
        minute = int(time[3:])
        current = hour * 60 + minute

        for step in range(1, 1441):
            candidate = (current + step) % 1440

            h = candidate // 60
            m = candidate % 60

            next_time = f"{h:02d}:{m:02d}"

            if all(ch in allowed or ch == ":" for ch in next_time):
                return next_time

        return time
```

## Code Explanation

We first collect the allowed digits:

```python
allowed = set(time)
allowed.remove(":")
```

For `"19:34"`, this gives:

```python
{"1", "9", "3", "4"}
```

Then we convert the input time into minutes since midnight:

```python
hour = int(time[:2])
minute = int(time[3:])
current = hour * 60 + minute
```

The loop tries each later minute:

```python
for step in range(1, 1441):
```

The modulo handles wraparound:

```python
candidate = (current + step) % 1440
```

Then we convert the minute count back to hour and minute:

```python
h = candidate // 60
m = candidate % 60
```

The formatting keeps leading zeroes:

```python
next_time = f"{h:02d}:{m:02d}"
```

So hour `1` and minute `5` become:

```python
"01:05"
```

Finally, we check whether the candidate uses only allowed digits:

```python
if all(ch in allowed or ch == ":" for ch in next_time):
    return next_time
```

The first valid candidate is returned immediately.

## Testing

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

    assert s.nextClosestTime("19:34") == "19:39"
    assert s.nextClosestTime("23:59") == "22:22"

    assert s.nextClosestTime("11:11") == "11:11"
    assert s.nextClosestTime("00:00") == "00:00"
    assert s.nextClosestTime("01:32") == "01:33"
    assert s.nextClosestTime("13:55") == "15:11"
    assert s.nextClosestTime("20:48") == "22:00"

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Expected | Why |
|---|---:|---|
| `"19:34"` | `"19:39"` | Official example |
| `"23:59"` | `"22:22"` | Wraps to next day |
| `"11:11"` | `"11:11"` | Same time appears again after one full day |
| `"00:00"` | `"00:00"` | Only digit `0` is available |
| `"01:32"` | `"01:33"` | Next minute-like valid candidate |
| `"13:55"` | `"15:11"` | Requires changing hour and minute |
| `"20:48"` | `"22:00"` | Requires skipping many invalid times |