# Short and simple O(1) Python solution

• The idea is really simple.
Generate all increments of the time given, and find the first time that has all the digits in the original time given.

``````def nextClosestTime(self, time):
digits = [int(y) for x in time.split(':') for y in x]
h, m = time.split(':')
while True:
h, m = (str(int(h)+1), '00') if int(m) == 59 else (h, str(int(m)+1))
h = '00' if int(h) > 23 else h
h = '0' + h if len(h) == 1 else h
m = '0' + m if len(m) == 1 else m
if all([int(x) in digits for x in h+m]):
return h + ':' + m
``````

• interesting, so basically keep moving the clock -
1 - keep increasing minutes by 1
2 - take care if minute exceeds 59, increase hour and if hour exceeds 23, reset hour to 0
3 - check if all digits in in original time are used, whichever occur first will be the answer.

Maximum iterations will be maximum number of minutes in a day - 24*60 - 1440. So its basically O(1) solution both in space and time.

``````class Solution(object):
def nextClosestTime(self, time):
"""
:type time: str
:rtype: str
"""
hour,minute = time.split(':')
digits = set(map(int,[ digit for digit in hour + minute ]))
while True:
hour, minute = int(hour), int(minute)
hour, minute = (hour, minute + 1) if minute < 59 else ((hour + 1)%24, 0)
hour = str(hour) if 10 <= hour < 24 else '0' + str(hour)
minute = str(minute) if 10 <= minute < 60 else '0' + str(minute)
current = set(map(int,[ digit for digit in hour + minute ]))
if not (current - digits): # current is proper subset of digits
break
return hour + ':' + minute
``````

• @sha256pki yeah, thats the idea.

• ``````h, m = time.split(':')[0], time.split(':')[1]
``````

Argh, my eyes! :-P

``    h, m = time.split(':')``

• @StefanPochmann I assumed only tuples can be unraveled like that, thanks for pointing that out. will change it.

• So by generating all times incrementally, you will be looking at 1440 values in the worst case, like sha256 mentioned. This is indeed O(1). I think I have a solution that does better in worst case time. -- Generate all permutations of the timestring. Because the string is 4 chars long, you will only ever look 256 permutations at worst. You can reduce these some if you check valid time strings only. This solution is O(n^n) where n is length of the string, and quickly goes haywire if you were to add seconds, but for 4-length strings, it behaves better in the worst case. Thanks for sharing your solution. Tell me what you think about mine.

• @mtu_wa_watu In fact every possible solution for this problem would be O(1), including the "O(n^n)" one you mentioned, since the input sice is bounded.
The big O notation is used to describe the growth rate of complexity when the input grows. It's kind of pointless here when the input don't grow.

• I thought about incrementing 1 minutes at a time, but it doesn't seem entirely necessary.
Because the cases are really limited...and that we do have a valid input, so it's guaranteed to have some 0, 1, or 2 that we can use to replace latter digits...
(Hope this doesn't hurt eye too much)

``````class Solution:
def nextClosestTime(self, time):
digits = sorted(list([d for d in time if d.isdigit()]))
minn = min(digits)

for d in digits:
if d > time[4] and d<="9":
return time[:4] + d

for d in digits:
if d > time[3] and d<="5":
return time[:3] + d + minn

for d in digits:
if d > time[1] and int(time[0]+d)<24:
return time[:1] + d + ':' + minn * 2

for d in digits:
if d > time[0] and int(d+time[1])<24:
return d + minn + ':' + minn * 2

return minn * 2 + ':' + minn * 2
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.