#1296

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Divide Array in Sets of K Consecutive Numbers

Determine if an integer array can be partitioned into sets of k consecutive numbers using array scanning and hash mapping techniques.

array hash table greedy sorting

Problem Statement

Given an integer array nums and a positive integer k, determine if it is possible to partition the array into sets of k consecutive numbers. Each number must be used exactly once in one of the sets.

Return true if such a partition exists, otherwise return false. For example, nums = [1,2,3,3,4,4,5,6] and k = 4 can be split into [1,2,3,4] and [3,4,5,6], so the output is true.

Examples

Example 1

Input: nums = [1,2,3,3,4,4,5,6], k = 4

Output: true

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

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

Each array should be divided in subarrays of size 3.

Constraints

1 <= k <= nums.length <= 105
1 <= nums[i] <= 109

Solution Approach

Count occurrences with a hash map

Build a frequency map of all numbers in nums to track availability. This ensures O(1) access when checking if a number can start or extend a consecutive sequence.

Iterate from smallest to largest

Sort unique numbers or use a min-heap to always select the smallest remaining number. Attempt to create a sequence of k consecutive numbers, decrementing their counts in the hash map. Failure occurs if any needed number is missing.

Check all numbers are used

After processing all numbers, confirm the hash map has zero remaining counts. If any number still has count > 0, return false. Otherwise, return true, confirming a valid consecutive partition.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) due to sorting or heap operations, where n is the array length. Hash map lookups for building and updating counts are O(1) each. Space complexity is O(n) to store frequency counts.

What Interviewers Usually Probe

Asks if duplicates affect sequence formation
Checks understanding of greedy consecutive construction
Observes handling of gaps in the array sequence

Common Pitfalls or Variants

Common pitfalls

Failing to decrement counts correctly for duplicates
Assuming sorted array without handling missing numbers
Using linear search instead of hash map, causing TLE for large n

Follow-up variants

Partition array into sets of k consecutive odd or even numbers
Allow sequences of length k but with at most one missing number
Return the actual groups instead of boolean result

FAQ

What is the main pattern for solving Divide Array in Sets of K Consecutive Numbers?

The primary pattern is array scanning combined with hash table lookup to efficiently track counts and form consecutive sequences.

Can this approach handle large arrays up to 10^5 elements?

Yes, using a hash map for counts and sorting or min-heap for smallest number selection keeps the algorithm efficient for large inputs.

How do duplicates in the array affect the solution?

Duplicates must be decremented in the frequency map as sequences are formed. Failing to do so can incorrectly report that partitioning is impossible.

What happens if a number is missing in the middle of a consecutive set?

If any required number is missing, the greedy sequence construction fails immediately and the algorithm returns false.

Is sorting necessary for Divide Array in Sets of K Consecutive Numbers?

Sorting helps quickly find the smallest available number to start sequences, but a min-heap or ordered map can be used as an alternative.

terminal

Solution

Solution 1: Hash Table + Sorting

First, we check if the length of the array $\textit{nums}$ is divisible by $\textit{k}$. If it is not divisible, it means the array cannot be divided into subarrays of length $\textit{k}$, and we return $\text{false}$ directly.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) % k:
            return False
        cnt = Counter(nums)
        for x in sorted(nums):
            if cnt[x]:
                for y in range(x, x + k):
                    if cnt[y] == 0:
                        return False
                    cnt[y] -= 1
        return True

Solution 2: Ordered Set

Similar to Solution 1, we first check if the length of the array $\textit{nums}$ is divisible by $\textit{k}$. If it is not divisible, it means the array cannot be divided into subarrays of length $\textit{k}$, and we return $\text{false}$ directly.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        if len(nums) % k:
            return False
        cnt = Counter(nums)
        for x in sorted(nums):
            if cnt[x]:
                for y in range(x, x + k):
                    if cnt[y] == 0:
                        return False
                    cnt[y] -= 1
        return True

Continue Practicing

#1338 reduce array size to the half #1481 least number of unique integers after k removals #1090 largest values from labels