Divide Array in Sets of K Consecutive Numbers

Divide Array in Sets of K Consecutive Numbers

What is this problem about?

The Divide Array in Sets of K Consecutive Numbers interview question asks you to determine if an array can be partitioned into sets of size $k$ where each set contains $k$ consecutive integers. For example, if $k=3$, a valid set could be [4, 5, 6]. Every number in the input array must be used exactly once.

Why is this asked in interviews?

Microsoft and Google use this problem to evaluate a candidate's proficiency with Hash Tables and Greedy interview patterns. It tests whether you can identify the "bottleneck" (the smallest available number) and realize that it must be the start of a consecutive sequence. It evaluation your ability to manage counts and efficiently verify group existence in a collection.

Algorithmic pattern used

This problem follows a Greedy approach with Frequency Counting.

1. Count the frequency of every number in the array using a TreeMap (to keep keys sorted).
2. While the map is not empty:
   • Get the smallest number $X$ in the map.
   • Try to form a group of $k$ starting from $X$: $X, X+1, \dots, X+k-1$.
   • For each number in the sequence, check if it exists in the map. If not, return false.
   • Decrement the count of each number in the map. If a count reaches zero, remove it.
3. If you can empty the map, return true.

Example explanation

Array: [1, 2, 3, 3, 4, 4, 5, 6], $k = 4$.

1. Counts: {1:1, 2:1, 3:2, 4:2, 5:1, 6:1}.
2. Smallest is 1. Form group: [1, 2, 3, 4].
3. New Counts: {3:1, 4:1, 5:1, 6:1}.
4. Smallest is 3. Form group: [3, 4, 5, 6].
5. Map is empty. Result: true.

Common mistakes candidates make

• Sorting every time: Re-sorting the array instead of using a frequency map.
• Missing the smallest element rule: Trying to form groups starting from random elements, which makes it impossible to know if a sequence is valid.
• Off-by-one: Checking for $X+k$ instead of $X+k-1$ as the end of the sequence.

Interview preparation tip

When a problem involves "consecutive" elements, sorting is almost always involved. A TreeMap or a sorted list of unique keys combined with a Hash Map is the standard way to implement a greedy "start from the bottom" strategy.