Short and simple O(1) Python solution


  • 4

    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
    

  • 3
    S

    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
    

  • 0

    @sha256pki yeah, thats the idea.


  • 5

    @johnyrufus16 said in Short and simple Python solution:

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

    Argh, my eyes! :-P

    Do this instead:

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

  • 0

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


  • 0
    M

    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.


  • 0
    E

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


  • 0
    D

    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
    

Log in to reply
 

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