Python O(n) time O(1) space


  • 0
    X
    class Solution(object):
        def isPossible(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            k = 3
            fs = [0] * k
            prev = float('-inf')
            for i, (v, f) in enumerate(freqs(nums)):
                if v != prev+1:
                    if any(x != fs[0] for x in fs):
                        return False
                    else:
                        fs = [0] * k                    
                else:
                    lack = fs[(i-1)%k] - f
                    if lack > fs[i%k]:
                        return False                    
                    elif lack > 0:
                        fs = [x-lack for x in fs]
                fs[i%k], prev = f, v
            return True
                    
    def freqs(arr):
        asz = len(arr)
        i = 0
        while i < asz:
            cnt = 1
            while i+1 < asz and arr[i] == arr[i+1]:
                i += 1
                cnt += 1
            yield arr[i], cnt
            i += 1
        yield float('inf'), 1
          
    

Log in to reply
 

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