Divide Array in Sets of K Consecutive Numbers
Medium · Greedy · Array · Hash Table · Greedy · Sorting
Problem
You are given an integer array nums and a positive integer k. Decide whether the whole array can be split into sets of k numbers where each set consists of k consecutive integers (such as [4, 5, 6] for k = 3).
Every element must be used exactly once. Return true if this is possible, otherwise false.
Examples
Input: nums = [4,2,3,3,5,4], k = 3 Output: True
The sets are [2,3,4] and [3,4,5].
Input: nums = [1,1,2,2,3,4], k = 3 Output: False
After [1,2,3], the remaining 1, 2, 4 are not consecutive.
Input: nums = [7,8,9,10], k = 1 Output: True
Every single number is its own set.
Constraints
- 1 <= k <= len(nums) <= 10^5
- 1 <= nums[i] <= 10^9
Approaches
- Baseline: build sets one at a time — time O(n^2), space O(n)
Follow-up
The smallest value forces its set, so the split, when it exists, is unique. The use cases return that split as a list of set starts, and find every set size that works for one array.
Related problems
Start free on Cariara · Coding problems · System design studio
