Divide Array in Sets of K Consecutive Numbers: Greedy Grouping

Given an array of integers nums and a positive integer k, determine whether you can divide the array into sets of k consecutive numbers. Each number must be used exactly once.

This is LeetCode 1296: Divide Array in Sets of K Consecutive Numbers, a medium problem that is functionally identical to Hand of Straights (LeetCode 846). If you can solve one, you can solve both.

Why this problem matters

This problem is a clean demonstration of greedy algorithms driven by frequency counting. The pattern of counting occurrences, iterating in sorted order, and greedily consuming elements appears across many interview problems. It also teaches you how to recognize when a greedy choice is provably optimal, which is a skill that transfers to scheduling, partitioning, and resource allocation problems.

The key insight

Think about the smallest number in the array. It must belong to some group, and it can only be the starting element of that group (nothing smaller exists to pair it with). So the group that begins at the smallest number is forced. Once you form that group and remove those numbers, the same logic applies to the next smallest remaining number.

This greedy choice is always correct: at every step, the smallest available number must start a new group. If the required consecutive numbers do not exist, the answer is False.

The solution

from collections import Counter

def isPossibleDivide(nums: list[int], k: int) -> bool:
    if len(nums) % k != 0:
        return False

    count = Counter(nums)

    for num in sorted(count):
        while count[num] > 0:
            for i in range(num, num + k):
                if count[i] <= 0:
                    return False
                count[i] -= 1

    return True

Here is how each piece works:

1. Divisibility check: if the total count of numbers is not divisible by k, you cannot form complete groups. Return False immediately.
2. Frequency map: use a Counter to record how many times each number appears.
3. Sorted iteration: process each unique number from smallest to largest. For each number that still has remaining copies, try to form a group of k consecutive values starting from that number.
4. Group formation: for each value in the range [num, num + k), check that it exists in the map and decrement its count. If any value has a count of 0 or less when you need it, return False.
5. Success: if all groups form without issues, return True.

Visual walkthrough

Each step shows the frequency map and highlights which values are being consumed. The greedy approach always picks the smallest available number and tries to extend it into a full consecutive group of size k.

Complexity analysis

The dominant cost is sorting the unique keys. Once sorted, each number is decremented exactly once across all groups, so the inner work is O(n) total. The frequency map takes O(n) space in the worst case where all values are unique.

The building blocks

1. Greedy with frequency counting

Count occurrences, then make locally optimal choices based on what remains. The same pattern appears in problems like Task Scheduler (schedule the most frequent task first) and Top K Frequent Elements (count, then select). The skeleton is always the same: build a counter, iterate in a strategic order, and consume greedily.

count = Counter(items)
for key in sorted(count):
    while count[key] > 0:
        # form a group starting at key
        pass

2. Sorted iteration over unique keys

Processing elements in sorted order enforces a natural grouping constraint. When you iterate from smallest to largest, you guarantee that each element is considered as a group starter before it could be consumed as a continuation of a later group. Sorting unique values (not the full array) keeps things efficient when duplicates are common.

for key in sorted(count):
    # process key as potential group start
    pass

Edge cases

• Array not divisible by k: nums = [1, 2, 3], k = 2. Length 3 is not divisible by 2. Return False before doing any work.
• Duplicate values: nums = [1, 1, 2, 2, 3, 3], k = 3. Two copies of 1, 2, 3 form two groups [1,2,3] and [1,2,3]. The while count[num] > 0 loop handles this naturally.
• Gaps in the sequence: nums = [1, 2, 4, 5, 6, 7], k = 3. Starting from 1, you need 1, 2, 3 but 3 is missing. Return False.
• k equals 1: every number forms its own group. Always True (as long as the length is valid).
• Single group: nums = [3, 4, 5], k = 3. One complete group. Return True.

From understanding to recall

The greedy logic is clean: check divisibility, count, sort, and build consecutive groups from the smallest number up. But in an interview, the details matter. Do you check divisibility first? Do you handle the while count[num] > 0 loop for duplicates? Do you remember to iterate over sorted(count) rather than sorted(nums)?

These small choices are where interviews trip people up. Reading the solution once gives you understanding, but not recall. Spaced repetition drills close that gap. You write the solution from scratch, then again a few days later, then a week later. After a few rounds, the pattern is automatic.

Related posts

• Hand of Straights - Same problem with different framing, grouping cards into consecutive runs
• Group Anagrams - Another grouping problem using hash maps
• Top K Frequent Elements - Frequency counting as a foundation for further processing

Divide Array in Sets of K Consecutive Numbers is a great example of how frequency counting and sorted greedy iteration turn a seemingly complex partitioning problem into something simple. CodeBricks breaks this down into its core building blocks and drills them independently with spaced repetition, so the full solution writes itself when you need it.