Skip to main content
Talentd

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

MediumArrayHash TableGreedySorting29 min readAsked at: Google, Waymo
Practice this problem

Problem Statement

Given an array of integers nums and a positive integer k, check whether it is possible to divide this array into sets of k consecutive numbers.

Return true if it is possible. Otherwise, return false.

 

Example 1:

Input: nums = [1,2,3,3,4,4,5,6], k = 4
Output: true
Explanation: 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
Explanation: 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
Explanation: Each array should be divided in subarrays of size 3.

 

Constraints:

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

 

Note: This question is the same as 846: https://leetcode.com/problems/hand-of-straights/

Approach Overview

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.

Approach 1: Dynamic Programming Approach

This approach involves breaking the problem into overlapping subproblems, solving each just once, and storing their solutions - optimal substructure. It is efficient for problems with optimal substructure and overlapping subproblems.

This C code uses dynamic programming to solve a Fibonacci-like problem. It initializes an array 'dp' to store solutions of subproblems and then recursively fills this array with values.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), Space Complexity: O(n)

Try this approach in the editor →

Approach 2: Space Optimized Dynamic Programming

This approach is an optimization of the dynamic programming approach, aiming to reduce space complexity by storing only the last two results needed to compute the current state instead of the entire array.

This C code reduces the space complexity by maintaining only the last two calculated values, utilizing simple variables instead of an array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Hash Table + Sorting

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

Next, we use a hash table cnt to count the occurrences of each number in the array nums, and then we sort the array nums.

After sorting, we iterate through the array nums, and for each number x, if cnt[x] is not 0, we enumerate each number y from x to x + k - 1. If cnt[y] is 0, it means we cannot divide the array into subarrays of length k, and we return false directly. Otherwise, we decrement cnt[y] by 1.

After the loop, if no issues were encountered, it means we can divide the array into subarrays of length k, and we return true.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Ordered Set

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

Next, we use an ordered set sd to count the occurrences of each number in the array nums.

Then, we repeatedly extract the smallest value x from the ordered set and enumerate each number y from x to x + k - 1. If these numbers all appear in the ordered set with non-zero occurrences, we decrement their occurrence count by 1. If the occurrence count becomes 0 after the decrement, we remove the number from the ordered set; otherwise, it means we cannot divide the array into subarrays of length k, and we return false.

If we can successfully divide the array into subarrays of length k, we return true after completing the traversal.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n), Space Complexity: O(n)

Space Optimized Dynamic Programming

Time Complexity: O(n), Space Complexity: O(1)

Hash Table + Sorting—
Ordered Set—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Frequency MapO(n log n)O(n)General solution. Easy to reason about using sorting and hash counts.
Space Optimized DP / Greedy ExtensionO(n log n)O(n)When you want fewer redundant checks by extending existing sequences greedily.

Video Solution

846. Hand of Straights | 1296. Divide Array in Sets of K Consecutive Numbers | Sorting | Map • Aryan Mittal • 8,059 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Divide Array in Sets of K Consecutive Numbers easy or hard?
The problem is generally classified as Medium difficulty on coding platforms. The logic is straightforward once you recognize the greedy pattern with frequency counting, but handling duplicates and ensuring correct sequence formation can be tricky without sorting and proper hash map management.
Divide Array in Sets of K Consecutive Numbers Python/Java solution
In both Python and Java, the typical implementation uses a map or dictionary to store frequencies and processes numbers in sorted order. For each smallest available value, attempt to build a group of k consecutive numbers by decrementing counts in the map. If any required value is missing, return false; otherwise continue until all elements are used.
How to solve Divide Array in Sets of K Consecutive Numbers in O(n)?
Pure O(n) time is difficult because ordering of numbers is required to build consecutive groups. Most correct solutions first sort the array, resulting in O(n log n) complexity. After sorting, a hash map or greedy extension technique ensures each element is processed efficiently while forming valid sequences.
What is the best approach for Divide Array in Sets of K Consecutive Numbers?
The most reliable approach sorts the array and uses a hash map to track frequencies. For each smallest unused number, try forming a sequence of length k by checking x, x+1, ..., x+k-1. Decrement counts as you build groups. This greedy counting technique runs in O(n log n) time due to sorting and O(n) space for the frequency map.
Is Divide Array in Sets of K Consecutive Numbers asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at large tech companies including Amazon, Google, and Meta. The question tests understanding of hash maps, greedy grouping, and handling ordered sequences in arrays. Interviewers typically expect a frequency-map greedy solution with clear reasoning about consecutive ranges.
What data structure is used in Divide Array in Sets of K Consecutive Numbers?
The primary data structure is a hash table (frequency map) that stores how many times each number appears. Sorting the array ensures numbers are processed in increasing order. Some optimized solutions also maintain an additional map tracking sequences that end at a specific number.
What is the time complexity of Divide Array in Sets of K Consecutive Numbers?
The optimal solution runs in O(n log n) time because the array must be sorted before forming groups. After sorting, each element is processed a constant number of times using hash map lookups. Space complexity is O(n) for storing element frequencies and sequence tracking.

Ready to solve this problem?

Practice Divide Array in Sets of K Consecutive Numbers with our built-in code editor and test cases.

Practice on FleetCode
Previous

All Divisions With the Highest Score of a Binary Array

Next

Split Array into Consecutive Subsequences