LeetCode 1296 - Divide Array in Sets of K Consecutive Numbers

LeetCode Problem 1296

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy, Sorting

Solution

Problem Understanding

The problem gives us an integer array nums and an integer k. We need to determine whether it is possible to divide all numbers in the array into groups where:

• Each group contains exactly k numbers
• The numbers inside each group are consecutive integers
• Every element in the array must belong to exactly one group

The important detail is that duplicates are allowed in the input array, and the same number may appear in multiple groups if it appears multiple times in the array.

For example, if we have:

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

we can split it into:

[1,2,3,4]
[3,4,5,6]

Both groups contain consecutive numbers of length 4, and every element is used exactly once.

The output should be:

• true if such a partition is possible
• false otherwise

The constraints are important:

• nums.length can be as large as 10^5
• Values inside nums can be up to 10^9

These constraints immediately tell us that inefficient repeated scanning approaches will likely time out. We need an algorithm close to O(n log n).

One immediate observation is that if the total number of elements is not divisible by k, then forming equal-sized groups is impossible. This becomes an early rejection condition.

Another important insight is that consecutive sequences impose ordering requirements. Since sequences depend on neighboring values, sorting or maintaining ordered access becomes necessary.

Several edge cases can trip up naive solutions:

• Arrays whose length is not divisible by k
• Large duplicate counts
• Missing middle values in a sequence
• Multiple overlapping sequences competing for the same numbers
• k = 1, where every number alone forms a valid group
• Sparse large integers, such as [1000000,1000001,1000002]

The problem guarantees only positive integers, so we do not need to handle negatives or empty arrays.

Approaches

Brute Force Approach

A straightforward solution is to repeatedly:

1. Sort the array
2. Pick the smallest unused number
3. Try to build a consecutive sequence of length k
4. Remove those numbers from consideration
5. Repeat until all numbers are used

For example:

[1,2,3,3,4,4,5,6]

We pick 1, then search for 2, 3, 4.

After removing them:

[3,4,5,6]

Then we repeat.

This approach is correct because every valid grouping must include the smallest remaining number as the start of some consecutive sequence. However, repeated removals and repeated scans become very expensive.

If implemented with repeated list deletions or linear searches, the complexity can degrade toward O(n^2).

With n up to 100000, this is too slow.

Optimal Greedy Approach

The key observation is this:

If we always process numbers from smallest to largest, then whenever we encounter a number with remaining frequency, it must start a new sequence.

Why?

Because smaller numbers have already been processed. If the current number was supposed to appear in the middle of a sequence, that sequence would already have consumed it earlier.

This naturally leads to a greedy strategy:

1. Count the frequency of each number
2. Process numbers in sorted order
3. Whenever a number still has remaining occurrences:

• Start that many sequences from this number
• Ensure the next k - 1 consecutive numbers also exist with sufficient frequency
• Decrease their counts

A hash map is ideal for frequency counting, and sorting ensures numbers are processed in valid order.

This approach avoids repeated rescanning and achieves efficient performance.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeated searches and removals are too expensive
Optimal	O(n log n)	O(n)	Uses sorting plus greedy frequency counting

Algorithm Walkthrough

1. First, check whether the array length is divisible by k.

If len(nums) % k != 0, then forming groups of equal size is impossible. We can immediately return false. 2. Count the frequency of every number.

We use a hash map where:

frequency[number] = count

This allows constant-time lookup and updates. 3. Sort the array.

Processing numbers in ascending order is critical. We always want to start sequences from the smallest available number. 4. Iterate through each number in sorted order.

For each number:

• If its frequency is already zero, it has already been used in previous sequences, so we skip it.
• Otherwise, this number must become the start of one or more new consecutive groups.

5. Determine how many sequences must start here.

Suppose:

frequency[current] = count

Then we must create exactly count sequences starting at current. 6. Check the next k consecutive numbers.

For every value:

current, current + 1, ..., current + k - 1

we verify that its frequency is at least count.

If any number does not have enough occurrences, then forming valid groups is impossible. 7. Decrease frequencies.

Once validated, subtract count from each consecutive number.

This represents consuming those numbers into newly formed groups. 8. Continue until all numbers are processed.

If no contradiction occurs, return true.

Why it works

The correctness comes from always processing the smallest remaining number first.

If a number still has unused occurrences when we encounter it, those occurrences cannot belong to a sequence started earlier, because earlier sequences would already have consumed them. Therefore, they must start new sequences.

The greedy choice is forced, not optional. By validating and consuming the next consecutive numbers immediately, we ensure that every formed group is valid and no smaller-number dependency is violated later.

Python Solution

from collections import Counter
from typing import List

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        n = len(nums)

        if n % k != 0:
            return False

        frequency = Counter(nums)

        for number in sorted(nums):
            if frequency[number] == 0:
                continue

            group_count = frequency[number]

            for next_number in range(number, number + k):
                if frequency[next_number] < group_count:
                    return False

                frequency[next_number] -= group_count

        return True

The implementation begins with an early divisibility check. If the total number of elements cannot be evenly split into groups of size k, there is no reason to continue.

Next, the Counter object stores the frequency of every value. This gives efficient constant-time access when validating consecutive sequences.

The array is then processed in sorted order. Sorting guarantees that we always encounter the smallest remaining unused number first.

Inside the loop, if the current number's frequency is already zero, it means previous groups have already consumed all copies of that number, so we skip it.

Otherwise, the remaining frequency determines how many groups must begin with this number. We then verify that all required consecutive numbers exist with sufficient frequency.

If any required number is missing or insufficient, we immediately return False.

Otherwise, we decrement frequencies to represent consuming those elements into groups.

If the entire loop completes successfully, every number has been grouped correctly, so we return True.

Go Solution

package main

import (
	"sort"
)

func isPossibleDivide(nums []int, k int) bool {
	n := len(nums)

	if n%k != 0 {
		return false
	}

	frequency := make(map[int]int)

	for _, num := range nums {
		frequency[num]++
	}

	sort.Ints(nums)

	for _, num := range nums {
		if frequency[num] == 0 {
			continue
		}

		groupCount := frequency[num]

		for nextNum := num; nextNum < num+k; nextNum++ {
			if frequency[nextNum] < groupCount {
				return false
			}

			frequency[nextNum] -= groupCount
		}
	}

	return true
}

The Go implementation follows exactly the same logic as the Python version.

The primary difference is manual map handling instead of Python's Counter. Missing keys in Go maps default to zero, which naturally supports frequency checks.

The array is sorted using sort.Ints(nums).

Go integers safely handle the given constraints since values remain within standard 32-bit integer limits, and Go's int type is sufficient.

Worked Examples

Example 1

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

Initial frequency map:

Number	Count
1	1
2	1
3	2
4	2
5	1
6	1

Sorted array:

[1,2,3,3,4,4,5,6]

Process 1:

• frequency[1] = 1
• Need sequence: [1,2,3,4]

After decrementing:

Number	Count
1	0
2	0
3	1
4	1
5	1
6	1

Process 2:

• Already zero, skip

Process first 3:

• frequency[3] = 1
• Need sequence: [3,4,5,6]

After decrementing:

Number	Count
1	0
2	0
3	0
4	0
5	0
6	0

All elements successfully grouped.

Result:

true

Example 2

nums = [3,2,1,2,3,4,3,4,5,9,10,11]
k = 3

Sorted array:

[1,2,2,3,3,3,4,4,5,9,10,11]

Initial frequencies:

Number	Count
1	1
2	2
3	3
4	2
5	1
9	1
10	1
11	1

Process 1:

Need [1,2,3]

Updated counts:

Number	Count
1	0
2	1
3	2

Process 2:

Need [2,3,4]

Updated counts:

Number	Count
2	0
3	1
4	1

Process 3:

Need [3,4,5]

Updated counts:

Number	Count
3	0
4	0
5	0

Process 9:

Need [9,10,11]

Updated counts become zero.

Result:

true

Example 3

nums = [1,2,3,4]
k = 3

Array length:

4 % 3 != 0

Immediate failure.

Result:

false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(n)	Frequency map stores up to all distinct values

The sorting step requires O(n log n) time. The subsequent frequency processing is linear because each number is decremented a limited number of times overall.

The hash map may contain up to n distinct numbers, requiring O(n) additional space.

Test Cases

from typing import List

class Solution:
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        from collections import Counter

        if len(nums) % k != 0:
            return False

        frequency = Counter(nums)

        for number in sorted(nums):
            if frequency[number] == 0:
                continue

            count = frequency[number]

            for next_number in range(number, number + k):
                if frequency[next_number] < count:
                    return False

                frequency[next_number] -= count

        return True

solution = Solution()

assert solution.isPossibleDivide([1,2,3,3,4,4,5,6], 4) == True  # basic valid example
assert solution.isPossibleDivide([3,2,1,2,3,4,3,4,5,9,10,11], 3) == True  # multiple valid groups
assert solution.isPossibleDivide([1,2,3,4], 3) == False  # length not divisible by k
assert solution.isPossibleDivide([1,2,3,4], 1) == True  # every number alone works
assert solution.isPossibleDivide([1,2,4,5,6,7], 3) == False  # missing middle value
assert solution.isPossibleDivide([1,1,2,2,3,3], 3) == True  # duplicate-based grouping
assert solution.isPossibleDivide([1,1,2,2,2,3,3], 3) == False  # insufficient consecutive counts
assert solution.isPossibleDivide([1000000,1000001,1000002], 3) == True  # large values
assert solution.isPossibleDivide([1], 1) == True  # smallest valid input
assert solution.isPossibleDivide([1,2], 3) == False  # k larger than array length

Test	Why
[1,2,3,3,4,4,5,6], k=4	Standard valid grouping
[3,2,1,2,3,4,3,4,5,9,10,11], k=3	Multiple independent sequences
[1,2,3,4], k=3	Length divisibility failure
[1,2,3,4], k=1	Every element forms its own group
[1,2,4,5,6,7], k=3	Missing required consecutive number
[1,1,2,2,3,3], k=3	Duplicate frequencies handled correctly
[1,1,2,2,2,3,3], k=3	Uneven duplicate counts cause failure
[1000000,1000001,1000002], k=3	Large integer values
[1], k=1	Minimum valid constraints
[1,2], k=3	Group size exceeds array size

Edge Cases

One important edge case occurs when the array length is not divisible by k. This is the simplest impossible scenario, but it is easy to overlook. Without this check, the algorithm might perform unnecessary processing before eventually failing. The implementation handles this immediately with:

if len(nums) % k != 0:
    return False

Another critical edge case involves duplicate values with insufficient continuation numbers. Consider:

[1,1,2,2,2,3,3]

with k = 3.

There are two copies of 1, meaning we must create two sequences starting from 1. That requires two copies each of 2 and 3. Although there are enough 3s, the frequency relationships can become inconsistent later. The frequency map guarantees precise accounting and prevents overusing values.

A third important case is sparse values with large gaps, such as:

[1,2,3,10,11,12]

The algorithm correctly handles disconnected valid ranges because it processes each smallest remaining number independently. Consecutive validation only applies locally within each required group.

Another subtle edge case is k = 1. In this scenario, every individual number already forms a valid consecutive group of size one. The implementation naturally handles this because each iteration only checks the current number itself.

Finally, large integer values could cause concern in some languages, but the algorithm never performs arithmetic beyond adding at most k to a number. Since constraints stay within standard integer limits, both Python and Go safely handle all valid inputs.