1296. Divide Array in Sets of K Consecutive Numbers LeetCode Solution
In this guide, you will get 1296. Divide Array in Sets of K Consecutive Numbers LeetCode Solution with the best time and space complexity. The solution to Divide Array in Sets of K Consecutive Numbers problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Divide Array in Sets of K Consecutive Numbers
Given an array of integers nums and a positive integer k, check whether it is possible to divide this array into sets of k consecutive numbers.
Return true if it is possible. Otherwise, return false.
Example 1:
Input: nums = [1,2,3,3,4,4,5,6], k = 4
Output: true
Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].
Example 2:
Input: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
Output: true
Explanation: Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].
Example 3:
Input: nums = [1,2,3,4], k = 3
Output: false
Explanation: Each array should be divided in subarrays of size 3.
Constraints:
1 <= k <= nums.length <= 105
1 <= nums[i] <= 109
Note: This question is the same as 846: https://leetcode.com/problems/hand-of-straights/
Complexity Analysis
Time Complexity: O(m\log m + mk), where m = # of different nums
Space Complexity: O(m)
1296. Divide Array in Sets of K Consecutive Numbers LeetCode Solution in C++
class Solution {
public:
bool isPossibleDivide(vector<int>& nums, int k) {
map<int, int> count;
for (const int num : nums)
++count[num];
for (const auto& [start, _] : count) {
const int value = count[start];
if (value > 0)
for (int i = start; i < start + k; ++i) {
count[i] -= value;
if (count[i] < 0)
return false;
}
}
return true;
}
}; /* code provided by PROGIEZ */
1296. Divide Array in Sets of K Consecutive Numbers LeetCode Solution in Java
class Solution {
public boolean isPossibleDivide(int[] nums, int k) {
TreeMap<Integer, Integer> count = new TreeMap<>();
for (final int num : nums)
count.merge(num, 1, Integer::sum);
for (final int start : count.keySet()) {
final int value = count.getOrDefault(start, 0);
if (value > 0)
for (int i = start; i < start + k; ++i)
if (count.merge(i, -value, Integer::sum) < 0)
return false;
}
return true;
}
} // code provided by PROGIEZ
1296. Divide Array in Sets of K Consecutive Numbers LeetCode Solution in Python
class Solution:
def isPossibleDivide(self, nums: list[int], k: int) -> bool:
count = collections.Counter(nums)
for start in sorted(count):
value = count[start]
if value > 0:
for i in range(start, start + k):
count[i] -= value
if count[i] < 0:
return False
return True # code by PROGIEZ
