Date and Time: Aug 17, 2024, 21:25 (EST)
Link: https://leetcode.com/problems/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.
-
1 <= k <= nums.length <= 10^5
-
1 <= nums[i] <= 10^9
This question is the same as the previous question 846. Hand of Straights.
class Solution {
public boolean isPossibleDivide(int[] nums, int k) {
if (nums.length % k != 0) {
return false;
}
Map<Integer, Integer> count = new HashMap<>();
for (int i: nums) {
count.put(i, count.getOrDefault(i, 0) + 1);
}
PriorityQueue<Integer> minHeap = new PriorityQueue<>(count.keySet());
while (!minHeap.isEmpty()) {
int first = minHeap.peek();
for (int i = first; i < first + k; i++) {
if (!count.containsKey(i)) {
return false;
}
count.put(i, count.get(i) - 1);
if (count.get(i) == 0) {
if (i != minHeap.peek()) {
return false;
}
minHeap.poll();
}
}
}
return true;
}
}
Time Complexity:
Space Complexity: