Next Closest Time - Solution & Explanation

Problem Overview: Given a time in HH:MM format, return the next closest valid time that can be formed using only the digits already present in the original time. Digits can be reused any number of times, but the result must represent a valid 24‑hour clock time.

Approach 1: Minute Simulation with Hash Set (O(1) time, O(1) space)

Extract the four digits from the input time and store them in a hash set for constant‑time membership checks. Convert the current time into total minutes since midnight. Then simulate minute by minute: increment the minute count, wrap around using modulo 24 * 60, and rebuild the candidate time. Split the candidate back into digits and verify every digit exists in the set. The first valid match is the answer. The search space is bounded to 1440 minutes, so the complexity is constant in practice. This approach relies on simple string manipulation and avoids complicated generation logic.

Approach 2: Digit Enumeration / Backtracking (O(4^4) time, O(1) space)

Instead of scanning minute by minute, enumerate every possible 4‑digit combination using only the allowed digits. Use backtracking or iterative enumeration to generate all combinations for positions HHMM. For each candidate, validate that hours are 0–23 and minutes are 0–59. Convert the valid candidate into minutes and compute the time difference from the original time (handling wrap‑around at midnight). Track the smallest positive difference. This approach explores at most 4^4 = 256 combinations, making it effectively constant time. Enumeration provides tighter control over candidate generation and is often easier to reason about in interview explanations.

Recommended for interviews: The minute‑simulation approach is the most straightforward and is typically what interviewers expect first. It demonstrates clear reasoning: convert time to minutes, iterate, and validate digits using a hash set. The enumeration/backtracking approach shows stronger algorithmic thinking because you explicitly generate all valid candidates and compare distances. Starting with brute simulation proves correctness quickly; presenting enumeration as an optimization shows deeper understanding of bounded search spaces.