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:
-
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. -
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, returnfalse
. -
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. -
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
.
Solution Approach
The provided solution implements a greedy algorithm to solve the problem by using the following steps:
-
Counting Elements: The solution uses Python's
Counter
from thecollections
module to count the frequency of each integer in the inputnums
. ThisCounter
acts like a hash map, and it stores each unique number as a key and its frequency as the corresponding value.cnt = Counter(nums)
-
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.
for v in sorted(nums):
-
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 tov + k
.if cnt[v]: for x in range(v, v + k):
-
Validating Consecutive Numbers: For each number in the expected consecutive range
[v, v + k)
, check if the current numberx
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 returnsFalse
.if cnt[x] == 0: return False
-
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 numberx
is removed from the counter to prevent future unnecessary checks.cnt[x] -= 1 if cnt[x] == 0: cnt.pop(x)
-
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 caseTrue
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
-
Counting Elements: We count the frequency of each number using the
Counter
.from collections import Counter nums = [1, 2, 3, 3, 4, 4, 5, 6] cnt = Counter(nums) # Counter({3: 2, 4: 2, 1: 1, 2: 1, 5: 1, 6: 1})
-
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]
. -
Forming Consecutive Groups: We start from the smallest number and try to form a group of
k
consecutive numbers. Starting with1
, then2
,3
, and4
. -
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 one1
. - For
2
,cnt[2] = 1
, we can use one2
. - For
3
,cnt[3] = 2
, we can use one3
. - For
4
,cnt[4] = 2
, we can use one4
.
- For
-
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})
- After using the numbers for the first group
-
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 from3
, and we would need a sequence[3, 4, 5, 6]
.- For
3
,cnt[3] = 1
, use one3
. - For
4
,cnt[4] = 1
, use one4
. - For
5
,cnt[5] = 1
, use one5
. - For
6
,cnt[6] = 1
, use one6
.
After this sequence, our counter is empty, which means we have successfully used all numbers to form groups of
k
consecutive numbers. - For
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.
Solution Implementation
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
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
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
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
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
.
-
Sorting
nums
: The sort operation on the listnums
has a time complexity ofO(N log N)
, whereN
is the number of elements innums
. -
Counter Construction: Constructing the counter
cnt
isO(N)
because we go through the listnums
once. -
Nested Loop: The nested loop involves iterating over each number in the sorted
nums
and then an inner loop that iterates up tok
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 mostO(k)
before it's removed. -
The total number of decrements across all elements cannot exceed
N
(since each decrement corresponds to one element ofnums
), and since we have that outer loop that potentially could visit allN
elements, we would multiply this byk
giving usO(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 whereM
is the number of unique numbers innums
. In the worst case, if all numbers are unique,M
is equal toN
, giving us a space complexity ofO(N)
.
Therefore, the overall space complexity of the code is O(N)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!