1296. Divide Array in Sets of K Consecutive Numbers


Problem Description

Given an integer array nums and a positive integer k, the task is to determine whether the array can be divided into several sets of k consecutive numbers. To divide the array into sets of k consecutive numbers means to group the elements of the array such that each group contains k numbers and each number in a group follows the one before it with a difference of 1. The function should return true if such division is possible, otherwise, it should return false.

Intuition

To solve this problem, the intuition is to use a greedy approach. The steps followed are:

  1. Count the occurrences of each number in the array using a hash map or counter. This step helps to quickly find how many times a number appears in nums without sorting the entire array.

  2. Start from the smallest number in the array and try to build a consecutive sequence of length k. If the sequence cannot be formed due to a missing number, return false.

  3. If a consecutive sequence of length k starting from a number is successfully formed, reduce the count of the numbers used in the sequence. If the count drops to zero, remove the number from the counter to avoid unnecessary checks in further iterations.

  4. Repeat steps 2 and 3 until all numbers are used to form valid sequences or until you find a sequence that cannot be completed.

Using this approach, the solution checks in a sorted order if there are enough consecutive numbers following the current number to form a group of k elements. If at any point there aren't enough consecutive numbers to form a group of k, the function returns false. On the other hand, if all numbers can be grouped successfully, the function returns true.

Learn more about Greedy and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Solution Approach

The provided solution implements a greedy algorithm to solve the problem by using the following steps:

  1. Counting Elements: The solution uses Python's Counter from the collections module to count the frequency of each integer in the input nums. This Counter acts like a hash map, and it stores each unique number as a key and its frequency as the corresponding value.

    1cnt = Counter(nums)
  2. Sorting and Iterating: After counting, the code sorts the unique numbers and iterates over them. The sorting ensures that we check for consecutive sequences starting with the smallest number.

    1for v in sorted(nums):
  3. Forming Consecutive Groups: Inside the loop, we check if the current number's count is non-zero, indicating that it hasn't been used up in forming a previous group. If the count is non-zero, the nested loop tries to form a group starting from this number v up to v + k.

    1if cnt[v]:
    2    for x in range(v, v + k):
  4. Validating Consecutive Numbers: For each number in the expected consecutive range [v, v + k), check if the current number x is present in the counter (i.e., its count is not zero). If it is zero, this indicates that a consecutive sequence cannot be formed, and the function returns False.

    1if cnt[x] == 0:
    2    return False
  5. Updating the Counter: When a number x is found, its count is decremented since it's being used to form the current sequence. If the count reaches zero after decrementing, the number x is removed from the counter to prevent future unnecessary checks.

    1cnt[x] -= 1
    2if cnt[x] == 0:
    3    cnt.pop(x)
  6. Completing the Iteration: This process continues until either a missing number is found (in which case False is returned), or all numbers are successfully grouped (in which case True is returned when the loop finishes).

Through these steps, the algorithm ensures that all possible consecutive sequences of length k are checked and formed, validating the possibility of dividing the array into sets of k consecutive numbers accurately.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal order?

Example Walkthrough

Let's illustrate the solution approach with an example:

Suppose we have an array nums = [1, 2, 3, 3, 4, 4, 5, 6] and k = 4. We want to find out if it's possible to divide this array into sets of k (4) consecutive numbers.

Following the solution approach:

  1. Counting Elements: We count the frequency of each number using the Counter.

    1from collections import Counter
    2nums = [1, 2, 3, 3, 4, 4, 5, 6]
    3cnt = Counter(nums)
    4# Counter({3: 2, 4: 2, 1: 1, 2: 1, 5: 1, 6: 1})
  2. Sorting and Iterating: We sort the nums and iterate over the distinct values. Here, the sorted unique values would be [1, 2, 3, 4, 5, 6].

  3. Forming Consecutive Groups: We start from the smallest number and try to form a group of k consecutive numbers. Starting with 1, then 2, 3, and 4.

  4. Validating Consecutive Numbers: We check if each of these consecutive numbers is present in the counter with a non-zero count.

    • For 1, cnt[1] = 1, thus we can use one 1.
    • For 2, cnt[2] = 1, we can use one 2.
    • For 3, cnt[3] = 2, we can use one 3.
    • For 4, cnt[4] = 2, we can use one 4.
  5. Updating the Counter: After decrementing, if any count becomes zero, we remove the number from the counter.

    • After using the numbers for the first group [1, 2, 3, 4], our counter updates to:
    • Counter({3: 1, 4: 1, 5: 1, 6: 1})
  6. Completing the Iteration: We repeat the process for the next smallest number with a non-zero count, which in this updated counter is 3. We try to form the next group starting from 3, and we would need a sequence [3, 4, 5, 6].

    • For 3, cnt[3] = 1, use one 3.
    • For 4, cnt[4] = 1, use one 4.
    • For 5, cnt[5] = 1, use one 5.
    • For 6, cnt[6] = 1, use one 6.

    After this sequence, our counter is empty, which means we have successfully used all numbers to form groups of k consecutive numbers.

Since no step failed and we could form two groups [1, 2, 3, 4] and [3, 4, 5, 6] each with 4 consecutive numbers, the function would return True. Hence, it is possible to divide the given array nums into sets of k (4) consecutive numbers.

Not Sure What to Study? Take the 2-min Quiz:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Python Solution

1from collections import Counter
2
3class Solution:
4    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
5        # Create a frequency count for all the numbers in nums
6        num_count = Counter(nums)
7      
8        # Loop over each number after sorting nums
9        for num in sorted(nums):
10            # If this number is still in the count dictionary
11            if num_count[num]:
12                # Attempt to create a consecutive sequence starting at this number
13                for x in range(num, num + k):
14                    # If any number required for the sequence does not exist, return False
15                    if num_count[x] == 0:
16                        return False
17                    # Decrease the count for this number since it's used in the sequence
18                    num_count[x] -= 1
19                    # If the count drops to zero, remove it from the dictionary
20                    if num_count[x] == 0:
21                        num_count.pop(x)
22                      
23        # If the entire loop completes without returning False, it means all sequences can be formed
24        return True
25

Java Solution

1import java.util.Arrays;
2import java.util.HashMap;
3import java.util.Map;
4
5class Solution {
6  
7    /**
8     * Checks if it is possible to divide the array into consecutive subsequences of length k.
9     *
10     * @param nums Input array of integers.
11     * @param k Length of the consecutive subsequences.
12     * @return true if division is possible, false otherwise.
13     */
14    public boolean isPossibleDivide(int[] nums, int k) {
15        // Create a map to store the frequency of each number in the input array.
16        Map<Integer, Integer> frequencyMap = new HashMap<>();
17        for (int num : nums) {
18            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
19        }
20
21        // Sort the input array to ensure the numbers are in ascending order.
22        Arrays.sort(nums);
23
24        // Iterate over the sorted array to check if division into subsequences is possible.
25        for (int num : nums) {
26            // Only start a sequence if the current number is still in the frequencyMap.
27            if (frequencyMap.containsKey(num)) {
28                // Attempt to create a subsequence of length k starting with the current number.
29                for (int i = num; i < num + k; ++i) {
30                    // If the current number is not in the frequencyMap, division is not possible.
31                    if (!frequencyMap.containsKey(i)) {
32                        return false;
33                    }
34                    // Decrease the frequency of the current number.
35                    frequencyMap.put(i, frequencyMap.get(i) - 1);
36                    // If the frequency of a number becomes 0, remove it from the map.
37                    if (frequencyMap.get(i) == 0) {
38                        frequencyMap.remove(i);
39                    }
40                }
41            }
42        }
43
44        // If the loop completes, then division into subsequences of length k is possible.
45        return true;
46    }
47}
48

C++ Solution

1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4
5class Solution {
6public:
7    // Function to determine if it is possible to divide the vector of integers into groups of size 'k'
8    // with consecutive numbers.
9    bool isPossibleDivide(std::vector<int>& nums, int k) {
10        // Creating a frequency map to count occurrences of each number
11        std::unordered_map<int, int> frequencyMap;
12        for (int num : nums) {
13            ++frequencyMap[num];
14        }
15
16        // Sort the input vector to process numbers in ascending order
17        std::sort(nums.begin(), nums.end());
18
19        // Process each number in the sorted vector
20        for (int num : nums) {
21            // If there is still a count for this number, we need to form a group starting with this number
22            if (frequencyMap.find(num) != frequencyMap.end()) {
23                // Attempt to create a group of 'k' consecutive numbers
24                for (int i = num; i < num + k; ++i) {
25                    // If any number required to form the group is missing, return false
26                    if (!frequencyMap.count(i)) {
27                        return false;
28                    }
29                    // Decrement the count for the current number in the group
30                    if (--frequencyMap[i] == 0) {
31                        // If the count reaches zero, remove the number from the frequency map
32                        frequencyMap.erase(i);
33                    }
34                }
35            }
36        }
37
38        // If the function hasn't returned false, it's possible to divide the numbers as required
39        return true;
40    }
41};
42

Typescript Solution

1function isPossibleDivide(nums: number[], k: number): boolean {
2  // Create a frequency map to count occurrences of each number
3  const frequencyMap: Record<number, number> = {};
4  for (const num of nums) {
5    frequencyMap[num] = (frequencyMap[num] || 0) + 1;
6  }
7
8  // Sort the input array to process numbers in ascending order
9  nums.sort((a, b) => a - b);
10
11  // Process each number in the sorted array
12  for (const num of nums) {
13    // If there is still a count for this number, we need to form a group starting with it
14    if (num in frequencyMap) {
15      // Attempt to create a group of 'k' consecutive numbers
16      for (let i = num; i < num + k; i++) {
17        // If any number required to form the group is missing, return false
18        if (!(i in frequencyMap)) {
19          return false;
20        }
21        // Decrement the count for the current number in the group
22        if (--frequencyMap[i] === 0) {
23          // If the count reaches zero, remove the number from the frequency map
24          delete frequencyMap[i];
25        }
26      }
27    }
28  }
29
30  // If the function hasn't returned false, it's possible to divide the numbers as required
31  return true;
32}
33
Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Time and Space Complexity

Time Complexity

The time complexity of the given code is determined by a few factors: the sorting of the input list nums, the construction of the counter cnt, and the nested loop where we check and decrement the count for each element over the range from v to v + k.

  1. Sorting nums: The sort operation on the list nums has a time complexity of O(N log N), where N is the number of elements in nums.

  2. Counter Construction: Constructing the counter cnt is O(N) because we go through the list nums once.

  3. Nested Loop: The nested loop involves iterating over each number in the sorted nums and then an inner loop that iterates up to k times for each unique number that has a non-zero count.

  • It may seem like this gives us O(Nk), but this is not entirely correct because each element is decremented once, and once it hits zero, it is popped from the counter and never considered again. Therefore, each element contributes at most O(k) before it's removed.

  • The total number of decrements across all elements cannot exceed N (since each decrement corresponds to one element of nums), and since we have that outer loop that potentially could visit all N elements, we would multiply this by k giving us O(Nk).

So, combining these together, the total time complexity is O(N log N + N + Nk) = O(N log N + Nk). Since for large N, N log N dominates N, and Nk may either dominate or be dominated by N log N depending on the values of N and k, the final time complexity is often written with both terms.

Space Complexity

The space complexity is mostly determined by the counter cnt which stores a count of each unique number in nums.

  • The counter can have at most M entries where M is the number of unique numbers in nums. In the worst case, if all numbers are unique, M is equal to N, giving us a space complexity of O(N).

Therefore, the overall space complexity of the code is O(N).

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫