Next Closest Time — LeetCode 681 Python Solution
MediumLeetCode PremiumHash TableStringBacktrackingEnumeration
- Problem
- #681
- Pattern
- Backtracking
- Reading time
- 5 min
- Source
- leetcode.com
The problem
Given a time represented in the format "HH:MM", form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused.
Example
- Input
- time = "19:34"
- Output
- "19:39"
- Explanation
- The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.
Python solution
Python
class Solution:
def nextClosestTime(self, time: str) -> str:
def check(t):
h, m = int(t[:2]), int(t[2:])
return 0 <= h < 24 and 0 <= m < 60
def dfs(curr):
if len(curr) == 4:
if not check(curr):
return
nonlocal ans, d
p = int(curr[:2]) * 60 + int(curr[2:])
if t < p < t + d:
d = p - t
ans = curr[:2] + ':' + curr[2:]
return
for c in s:
dfs(curr + c)
s = {c for c in time if c != ':'}
t = int(time[:2]) * 60 + int(time[3:])
d = inf
ans = None
dfs('')
if ans is None:
mi = min(int(c) for c in s)
ans = f'{mi}{mi}:{mi}{mi}'
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Backtracking
Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 681. Next Closest Time is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.
The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 681. Next Closest Time?
- LeetCode 681. Next Closest Time is rated Medium on LeetCode.
- What is the time complexity of LeetCode 681. Next Closest Time?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 681. Next Closest Time?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 681. Next Closest Time cover?
- LeetCode 681. Next Closest Time is tagged Hash Table, String, Backtracking and Enumeration on LeetCode.
- Is LeetCode 681. Next Closest Time a premium problem?
- Yes. LeetCode 681. Next Closest Time is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.