Divide Array In Sets Of K Consecutive Numbers - Leetcode Solution

Problem Statement: Given an array of integers nums and a positive integer k, divide the array into some number of disjoint sets each containing k consecutive numbers.

Return true if you can divide the array into such disjoint sets, or false otherwise.

Solution: To solve this problem, we can make use of a hash map to keep track of the frequency of each element in the array. We can then iterate through the array and for each element, we check if it is the start of a new sequence of k consecutive elements. If it is, we decrement the frequency of the k consecutive elements in the hash table. If we encounter an element that is not the start of a new sequence, we check if it can be added to an existing sequence. If it can be added, we decrement its frequency in the hash table and move on to the next element.

If we encounter an element that cannot be added to any existing sequence, we return false because we cannot divide the array into disjoint sets of k consecutive numbers.

In other words, we greedily try to group k consecutive elements starting from the smallest available element until we can no longer form a sequence.

Here is the step by step algorithm for our solution:

1. Sort the array in ascending order.
2. Create a hash map to keep track of the frequency of each element in the array.
3. For each element in the array: a. If the frequency of the element is 0, skip it. b. If the frequency of the element is greater than 0, check if it is the start of a new sequence. i. If it is the start of a new sequence, decrement the frequency of the remaining k-1 elements in the hash table. ii. If it is not the start of a new sequence, check if it can be added to any existing sequence. 1. If it can be added to an existing sequence, decrement its frequency in the hash table. 2. If it cannot be added to any existing sequence, return false.
4. If we have successfully gone through the entire array without returning false, return true.

Here is the implementation of the above algorithm in Python:

def isPossibleDivide(nums: List[int], k: int) -> bool:
    if len(nums) % k != 0:
        return False
    
    freq = {}
    for num in nums:
        freq[num] = freq.get(num, 0) + 1
    
    nums.sort()
    
    for num in nums:
        if freq[num] == 0:
            continue
            
        freq[num] -= 1
        for i in range(1, k):
            if freq.get(num + i, 0) > 0:
                freq[num + i] -= 1
            else:
                return False
                
    return True

Time Complexity: The time complexity of the above solution is O(n log n) due to sorting of the input array. The for loop that iterates over the input array has a worst-case time complexity of O(n*k) where n is the size of the array and k is the length of a sequence. However, since we are iterating over each element only once and using a hash map to keep track of the frequency, the average time complexity of the for loop is much lower.

Space Complexity: The space complexity of the above solution is O(n) due to the hash map used to store the frequency of each element in the input array.

1