Divide Array in Sets of K Consecutive Numbers LeetCode solution in Python

1
class Solution:
2
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
3
        # if we see x, we expect to see x+1 later
4
        #   and then x+2 after that
5
        #   and then x+3 after that
6

7
        # so maybe we can enqueue (x+1, k-2)  === (next number expected, count after x+1)
8
        #   e.g. k == 2: find x, enqueue (x+1, 0)
9

10
        # for each x:
11
        #   if front of queue has x, pop it. Re-enqueue with rem-1 if rem, else we finished a length k sequence
12
        #   if front of queue has x' < x, we have a gap. return False
13
        #   otherwise we found the start of a new sequence: append (x+1, k-2)
14
        #     meaning we found x (1), we're looking for x+1 (another 1), and after that we should find another k-2 numbers
15

16
        if k == 1:
17
            return True  # length 1 sequences are trivial
18

19
        nums.sort()
20
        q = deque()
21
        for n in nums:
22
            if not q or q[0][0] > n:
23
                q.append((n + 1, k - 2))
24
            elif q[0][0] == n:
25
                _, rem = q.popleft()
26
                if rem:
27
                    q.append((n + 1, rem - 1))
28
                # else: end of len k sequence
29
            else:
30
                return False  # found n > next expected, so we can't complete an earlier sequence
31

32
        if q:
33
            return False  # expected at least one more element to finish a sequence
34
        else:
35
            return True