Divide Array in Sets of K Consecutive Numbers - Solution & Explanation

Problem Overview: You receive an integer array and a value k. The task is to check whether the array can be split into groups of size k such that every group forms k consecutive numbers. Each element must be used exactly once. If all numbers can be arranged into these consecutive groups, return true; otherwise return false.

Approach 1: Dynamic Programming with Frequency Map (O(n log n) time, O(n) space)

Start by sorting the array so numbers are processed in increasing order. Build a frequency map using a hash table to track how many times each number appears. Iterate through the sorted numbers, and whenever a number still has remaining frequency, attempt to form a consecutive group starting from that value. For every value x, decrement counts for x, x+1, ..., x+k-1. If any required number is missing or its count becomes negative, forming valid groups is impossible. This approach behaves like dynamic programming because each decision (starting a sequence at a number) updates state stored in the frequency map. Sorting ensures smaller sequences are resolved before larger ones, avoiding conflicts.

This method relies heavily on efficient lookups in a hash table and ordered traversal enabled by sorting. It works well for general inputs and is the most common solution pattern used in interviews.

Approach 2: Space Optimized Dynamic Programming / Greedy Extension (O(n log n) time, O(n) space)

Instead of repeatedly checking each sequence independently, track how many sequences are currently expecting the next number. After sorting the array, maintain two hash maps: one for remaining frequencies and another that records how many sequences end at a specific number. When processing a value x, you first try to extend an existing sequence ending at x-1. If such a sequence exists, decrement its count and extend it to end at x. If no sequence can be extended, attempt to start a new group x, x+1, ..., x+k-1 by verifying that the next k-1 numbers exist in the frequency map.

This greedy strategy minimizes redundant checks because sequences grow naturally instead of being rebuilt from scratch. It still depends on ordered processing through arrays and leverages ideas from greedy algorithms. Memory usage is slightly more efficient because the algorithm tracks only active sequences instead of repeatedly validating entire ranges.

Recommended for interviews: The frequency-map greedy approach is what most interviewers expect. Sorting plus a hash map clearly demonstrates understanding of array ordering and counting techniques. Showing the optimized greedy extension approach signals stronger algorithmic thinking because it avoids unnecessary sequence reconstruction while maintaining the same asymptotic complexity.