Divide Array in Sets of K Consecutive Numbers
MedPrompt
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 <= 1051 <= nums[i] <= 109
Note: This question is the same as 846: https://leetcode.com/problems/hand-of-straights/
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves sorting the array first to make finding consecutive numbers easier. Then, it repeatedly scans the array to find and form groups of k consecutive numbers, marking used elements along the way.
Algorithm
- First, perform a preliminary check: if the length of the array
numsis not divisible byk, it's impossible to partition it, so returnfalse. - Sort the array
numsin ascending order. - Use a boolean array
usedof the same size asnumsto keep track of which numbers have already been placed into a group. Initially, all elements are marked as not used. - Iterate through the sorted array
numsfrom left to right. For each numbernums[i]:- If
nums[i]has already been used (i.e.,used[i]is true), skip it. - If it's not used, we try to form a new group of
kconsecutive numbers starting withnums[i]. - We search for the next
k-1consecutive numbers (nums[i]+1,nums[i]+2, ...,nums[i]+k-1) in the rest of the array. - For each required number, we perform a linear scan from the position
i+1. If we find the required numbernums[j]and it hasn't been used yet, we mark it as used (used[j] = true) and continue searching for the next number in the sequence. - If any of the
k-1consecutive numbers cannot be found, it's impossible to form the required groups, so we returnfalse.
- If
- If we successfully iterate through the entire array and group all numbers, return
true.
Walkthrough
The brute-force method begins by sorting the input array nums. This brings numbers that could potentially form a consecutive sequence close to each other. An essential pre-condition is that the array's length must be a multiple of k; otherwise, a valid partition is impossible. We use an auxiliary boolean array, used, to track which elements have been assigned to a set. We iterate through each element of the sorted array. If an element nums[i] hasn't been used, we treat it as the start of a new potential set. We then attempt to find the subsequent k-1 consecutive integers (nums[i]+1, nums[i]+2, etc.) by scanning the rest of the array. If we find a required integer that is not yet used, we mark it as used and proceed to look for the next one. If at any point a required integer for a sequence cannot be found, we conclude that a valid partition is not possible and return false. If we manage to group all numbers this way, we return true.
import java.util.Arrays; class Solution { public boolean isPossibleDivide(int[] nums, int k) { int n = nums.length; if (n % k != 0) { return false; } Arrays.sort(nums); boolean[] used = new boolean[n]; for (int i = 0; i < n; i++) { if (used[i]) { continue; } // Start a new group with nums[i] used[i] = true; int needed = k - 1; int lastNum = nums[i]; if (needed > 0) { for (int j = i + 1; j < n; j++) { if (!used[j] && nums[j] == lastNum + 1) { used[j] = true; lastNum = nums[j]; needed--; if (needed == 0) { break; } } } } if (needed > 0) { return false; } } return true; }}Complexity
Time
O(N^2). Sorting takes O(N log N). The main loop runs N times. Inside, for each of the N/k groups, we might scan a large portion of the array k-1 times. This leads to a complexity that is roughly quadratic.
Space
O(N), where N is the number of elements in `nums`. This is for the `used` array. The space for sorting can also be up to O(N) depending on the implementation.
Trade-offs
Pros
Conceptually simple and easy to understand.
Works for small inputs.
Cons
Highly inefficient due to nested loops, leading to a quadratic time complexity.
Will result in a 'Time Limit Exceeded' error on large inputs.
Solutions
Solution
class Solution {public boolean isPossibleDivide(int[] nums, int k) { Map<Integer, Integer> cnt = new HashMap<>(); for (int v : nums) { cnt.put(v, cnt.getOrDefault(v, 0) + 1); } Arrays.sort(nums); for (int v : nums) { if (cnt.containsKey(v)) { for (int x = v; x < v + k; ++x) { if (!cnt.containsKey(x)) { return false; } cnt.put(x, cnt.get(x) - 1); if (cnt.get(x) == 0) { cnt.remove(x); } } } } return true; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.