Divide Array in Sets of K Consecutive Numbers

Problem Id: 1296 Difficulty: Medium Tag: Array Tag: Greedy


Intuition

Sort all the numbers. For the least number i, there should be i, i + 1, ..., i + k - 1 to make up the first group. And for all i + j where j < k, we could always use the first one to be in the first group.

So we use greedy, handle with the numbers in increasing order. Once we face a new number, we first check if it is required for the groups starts with previous numbers. If yes, we mark it into the group. If no, we create a new group starts with this number by adding count[i] by 1 for all number <= i < number + k.

Solution


from collections import defaultdict


class Solution:
    def isPossibleDivide(self, nums, k) -> bool:
        nums.sort()
        count = defaultdict(int)
        for num in nums:
            if count[num] <= 0:
                for l in range(k):
                    count[num + l] += 1
            count[num] -= 1
        for v in count.values():
            if v > 0:
                return False
        return True