Python O(n) solution


  • 0
    F

    seq_len stores the length of consecutive sequences. It is sorted in ascending order, we add number to the shortest sequence first.

    def isPossible(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        prev = None
        seq_len = []  # seq_len
    
        for val, g in itertools.groupby(nums):
            count = len(list(g))  # the number of val in the list
            if prev == val - 1:
                if count >= len(seq_len): 
                    seq_len = [1]*(count-len(seq_len)) + [x + 1 for x in seq_len]
                else:
                    if any([x < 3 for x in seq_len[count:]]):
                        return False
                    else:
                        seq_len = [x + 1 for x in seq_len[:count]]
            else:         
                if any([x < 3 for x in seq_len]):
                    return False
                seq_len = [1] * count
    
            prev = val
    
        if any([x < 3 for x in seq_len]):
            return False
    
        return True
    

Log in to reply
 

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