Short and simple O(1) Python solution

  • 3

    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

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

    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

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

Log in to reply

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