LeetCode 681 - Next Closest Time

The problem gives us a valid time string in the format "HH:MM" and asks us to construct the next chronological time using only the digits already present in the original time. The important detail is that digits may be reused any number of times.

leetcodemediumhash-tablestringbacktrackingenumeration

LeetCode Problem 681

Difficulty: 🟡 Medium
Topics: Hash Table, String, Backtracking, Enumeration

Solution

Problem Understanding

The problem gives us a valid time string in the format "HH:MM" and asks us to construct the next chronological time using only the digits already present in the original time.

The important detail is that digits may be reused any number of times. If the input is "19:34", the allowed digits are {1, 9, 3, 4}. We can use any of those digits repeatedly to form another valid time. The goal is to find the valid time that occurs next in chronological order.

The phrase "next closest time" means the smallest positive time difference moving forward minute by minute. If no larger valid time exists within the same day, the answer wraps to the next day. For example, from "23:59" the next valid time is "22:22" on the following day.

The input constraints are extremely small. The input length is always 5, and the time is guaranteed to be valid. Since a day only contains 24 × 60 = 1440 minutes, even brute force solutions are feasible. This small search space is the key observation that allows us to use a very direct and reliable approach.

Several edge cases are important:

  • The next valid time may occur on the next day.
  • The current time itself cannot be returned immediately because we need the next occurrence.
  • Some inputs only allow a single valid time. For example, "11:11" can only produce "11:11", so the answer wraps around after a full day.
  • Times near midnight such as "23:59" require proper modular arithmetic.
  • Candidate times must still satisfy valid clock constraints, hours less than 24 and minutes less than 60.

Approaches

Brute Force Approach

The brute force solution generates every possible 4-digit combination using the available digits and checks whether it forms a valid time.

If there are at most 4 unique digits, there are at most:

$$4^4 = 256$$

possible combinations. For each combination, we validate the hour and minute values, convert the valid time into total minutes, and compute the forward time difference from the original time.

We then choose the valid candidate with the smallest positive difference.

This approach is completely correct because it exhaustively checks every possible valid time constructible from the allowed digits. Since the search space is tiny, performance is acceptable.

However, it still performs unnecessary generation and validation of many impossible combinations.

Optimal Approach

The better observation is that there are only 1440 possible minutes in a day. Instead of generating all combinations, we can simply move forward minute by minute from the current time and check whether the resulting time uses only allowed digits.

This works well because the first valid time encountered is automatically the correct answer. We never need to compare candidates or compute minimum differences manually.

The algorithm becomes very clean:

  1. Convert the input time into minutes.
  2. Store the allowed digits in a set.
  3. Repeatedly advance the time by one minute using modulo 1440.
  4. Convert the candidate back into "HH:MM" format.
  5. Check whether every digit belongs to the allowed set.
  6. Return the first valid candidate.

Since we examine at most 1440 times, the runtime is effectively constant.

Approach Time Complexity Space Complexity Notes
Brute Force O(4^4) = O(1) O(1) Generates all possible digit combinations
Optimal O(1440) = O(1) O(1) Simulates forward minute-by-minute search

Algorithm Walkthrough

  1. Extract all usable digits from the input time.

We ignore the colon and place the remaining digits into a hash set. A set is ideal because membership checks are constant time. If the input is "19:34", the allowed digit set becomes {'1', '9', '3', '4'}. 2. Convert the current time into total minutes.

Converting time into a single integer simplifies time arithmetic. For example:

$$19 \times 60 + 34 = 1174$$

This representation makes incrementing the clock straightforward. 3. Start an infinite loop that advances time by one minute.

Each iteration computes:

$$(current + 1) \bmod 1440$$

The modulo operation handles wraparound at midnight automatically. 4. Convert the candidate minute count back into hour and minute format.

We compute:

  • hour = current // 60
  • minute = current % 60

Then format the candidate as a zero-padded string like "19:39". 5. Verify that every digit in the candidate time belongs to the allowed set.

We skip the colon and examine only numeric characters. If all digits are present in the allowed set, this candidate is valid. 6. Return the first valid candidate encountered.

Because we search minute by minute in chronological order, the first valid time must be the next closest time.

Why it works

The algorithm checks times in strictly increasing chronological order starting immediately after the input time. Since every possible future minute is examined exactly once before repeating, the first valid constructible time encountered must be the smallest forward time difference. Therefore, the returned result is guaranteed to be the correct next closest time.

Python Solution

class Solution:
    def nextClosestTime(self, time: str) -> str:
        allowed_digits = set(time.replace(":", ""))

        current_minutes = int(time[:2]) * 60 + int(time[3:])

        while True:
            current_minutes = (current_minutes + 1) % 1440

            hours = current_minutes // 60
            minutes = current_minutes % 60

            candidate = f"{hours:02d}:{minutes:02d}"

            if all(char in allowed_digits for char in candidate if char != ":"):
                return candidate

The implementation begins by extracting the usable digits into a set. Using a set allows efficient membership testing when validating candidate times.

Next, the input time is converted into total minutes from midnight. This avoids dealing with hour and minute carry logic manually.

The loop continuously advances the clock by one minute. Using modulo 1440 ensures that after "23:59" the time correctly wraps back to "00:00".

For each candidate minute value, the code reconstructs a properly formatted time string using zero-padded formatting. This is important because times such as "01:05" must preserve leading zeros.

Finally, the all() check validates that every digit in the candidate belongs to the allowed set. The first valid candidate is immediately returned.

Go Solution

package main

import (
	"fmt"
)

func nextClosestTime(time string) string {
	allowedDigits := make(map[rune]bool)

	for _, ch := range time {
		if ch != ':' {
			allowedDigits[ch] = true
		}
	}

	hours := int(time[0]-'0')*10 + int(time[1]-'0')
	minutes := int(time[3]-'0')*10 + int(time[4]-'0')

	currentMinutes := hours*60 + minutes

	for {
		currentMinutes = (currentMinutes + 1) % 1440

		h := currentMinutes / 60
		m := currentMinutes % 60

		candidate := fmt.Sprintf("%02d:%02d", h, m)

		valid := true

		for _, ch := range candidate {
			if ch != ':' && !allowedDigits[ch] {
				valid = false
				break
			}
		}

		if valid {
			return candidate
		}
	}
}

The Go implementation follows the same logic as the Python version. A map[rune]bool is used instead of a Python set for constant-time digit lookup.

Go requires manual parsing of the time characters into integers because there is no direct slicing-to-int conversion like Python. The formatted candidate string is created using fmt.Sprintf("%02d:%02d", h, m) to preserve leading zeros.

No overflow concerns exist because all computations remain within the range of 0 to 1439.

Worked Examples

Example 1

Input:

"19:34"

Allowed digits:

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

Current time in minutes:

$$19 \times 60 + 34 = 1174$$

We now advance minute by minute.

Minute Value Candidate Valid? Reason
1175 19:35 No digit 5 not allowed
1176 19:36 No digit 6 not allowed
1177 19:37 No digit 7 not allowed
1178 19:38 No digit 8 not allowed
1179 19:39 Yes digits 1,9,3,9 all allowed

The algorithm returns:

"19:39"

Example 2

Input:

"23:59"

Allowed digits:

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

Current minutes:

$$23 \times 60 + 59 = 1439$$

The next increment wraps around:

Minute Value Candidate Valid?
0 00:00 No
1 00:01 No
... ... ...
1342 22:22 Yes

The algorithm eventually reaches "22:22" on the next day.

Complexity Analysis

Measure Complexity Explanation
Time O(1440) At most one full day of minute checks
Space O(1) Only a small digit set is stored

The runtime is effectively constant because the number of minutes in a day never changes. Even in the worst case, the algorithm checks only 1440 candidate times before repeating. The space usage is also constant because the digit set contains at most four unique digits.

Test Cases

solution = Solution()

assert solution.nextClosestTime("19:34") == "19:39"  # basic example
assert solution.nextClosestTime("23:59") == "22:22"  # wraps to next day
assert solution.nextClosestTime("11:11") == "11:11"  # only one possible time
assert solution.nextClosestTime("00:00") == "00:00"  # all zeros
assert solution.nextClosestTime("01:32") == "01:33"  # immediate next valid minute
assert solution.nextClosestTime("13:55") == "15:11"  # requires hour transition
assert solution.nextClosestTime("22:23") == "22:32"  # valid within same hour
assert solution.nextClosestTime("20:48") == "22:00"  # requires multiple carry operations
assert solution.nextClosestTime("15:51") == "15:55"  # repeated digit usage
assert solution.nextClosestTime("12:12") == "12:21"  # rearranged digits
Test Why
"19:34" Standard example case
"23:59" Tests midnight wraparound
"11:11" Tests single possible valid time
"00:00" Tests all-zero input
"01:32" Tests immediate next minute
"13:55" Tests hour transition
"22:23" Tests digit rearrangement
"20:48" Tests larger forward jumps
"15:51" Tests repeated digit reuse
"12:12" Tests mixed repeated digits

Edge Cases

One important edge case occurs when the next valid time is on the following day. Inputs such as "23:59" require wraparound handling. A naive implementation that only searches within the current day would fail. The modulo 1440 operation ensures the clock cycles correctly back to midnight.

Another tricky case occurs when only one valid time can ever be formed. For example, "11:11" contains only the digit 1. The only possible valid time is itself. The algorithm correctly handles this because it continues searching minute by minute until the full day cycle returns to "11:11" again.

Leading zeros are another common source of bugs. Times such as "01:05" must preserve the exact two-digit formatting for hours and minutes. Without zero-padding, a candidate like "1:5" would incorrectly omit digits and break validation logic. Using formatted strings such as f"{hours:02d}:{minutes:02d}" ensures correctness.

A final subtle edge case involves invalid intermediate combinations. Even if all digits are allowed, combinations like "29:99" are not valid clock times. The minute-by-minute simulation approach naturally avoids constructing invalid times because every generated candidate already comes from a valid minute count between 0 and 1439.