LeetCode 681: Next Closest Time

Problem Restatement

We are given a valid time string in the format:

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:

time = "19:34"

then the available digits are:

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

Example function shape:

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

Examples

Example 1:

time = "19:34"

Available digits:

1, 9, 3, 4

The next valid time is:

"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:

time = "23:59"

Available digits:

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:

"22:22"

First Thought: Generate All Times

There are only 24 hours and 60 minutes.

That means there are only:

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:

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

Then we try:

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:

     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:

time = "19:34"

Allowed digits:

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

Current minute:

19 * 60 + 34 = 1174

Now try later minutes:

So the answer is:

"19:39"

Now consider:

time = "23:59"

Allowed digits:

{'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:

"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.

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

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:

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

For "19:34", this gives:

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

Then we convert the input time into minutes since midnight:

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

The loop tries each later minute:

for step in range(1, 1441):

The modulo handles wraparound:

candidate = (current + step) % 1440

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

h = candidate // 60
m = candidate % 60

The formatting keeps leading zeroes:

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

So hour 1 and minute 5 become:

"01:05"

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

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

The first valid candidate is returned immediately.

Testing

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: