Divide Array in Sets of K Consecutive Numbers

Divide Array in Sets of K Consecutive Numbers - Problem

Given an array of integers nums and a positive integer k, determine whether it's possible to divide the array into sets of k consecutive numbers.

Return true if it's possible to divide the array into such sets, otherwise return false.

Example: If nums = [1,2,3,3,4,4,5,6] and k = 4, we can form two sets: [1,2,3,4] and [3,4,5,6], so return true.

Input & Output

Example 1 — Basic Case

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

› Output: true

💡 Note: We can form two groups of 4 consecutive numbers: [1,2,3,4] and [3,4,5,6]. Each number is used exactly once.

Example 2 — Impossible Case

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

› Output: false

💡 Note: We have 12 numbers, so we need 4 groups of 3. However, we can't form 4 complete consecutive sequences due to the gap at 9,10,11.

Example 3 — Single Group

$ Input: nums = [1,2,3,4], k = 4

› Output: true

💡 Note: Perfect case: exactly one group of 4 consecutive numbers [1,2,3,4].

Constraints

1 ≤ k ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,2,3,3,4,4,5,6] with k=4

Process

Group into consecutive sequences of length k

Output

Return true if possible, false otherwise

Key Takeaway

🎯 Key Insight: Always start forming groups from the smallest available number to ensure optimal grouping without conflicts

Asked in

a Amazon 45 G Google 38 f Facebook 32 M Microsoft 28

The key insight is to use frequency counting with greedy selection - always start forming groups from the smallest available number. The optimal approach counts frequencies and repeatedly selects the minimum number to start consecutive sequences. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Check Consecutive Sequences	O(n log n)	O(n)	Sort array and check if it can be split into consecutive sequences of length k
Brute Force with Backtracking	O(k^n)	O(n)	Try all possible ways to group numbers into consecutive sets
Frequency Count with Greedy Selection	O(n log n)	O(n)	Count frequencies and greedily form consecutive groups starting from smallest

Sort and Check Consecutive Sequences — Algorithm Steps

Sort the input array
Count frequency of each number
For each number, if it can start a sequence, form k consecutive numbers
Mark used numbers and continue

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Sort input array and count frequencies

Process in Order

For each number, try to form consecutive sequence

Update Counts

Decrease frequency counts as numbers are used

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_NUMS 10000
#define MAX_VAL 1000000

int counter[2*MAX_VAL + 1];
int offset = MAX_VAL;

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

bool solution(int* nums, int numsSize, int k) {
    if (numsSize % k != 0) return false;
    
    memset(counter, 0, sizeof(counter));
    for (int i = 0; i < numsSize; i++) {
        counter[nums[i] + offset]++;
    }
    
    qsort(nums, numsSize, sizeof(int), compare);
    
    for (int i = 0; i < numsSize; i++) {
        if (counter[nums[i] + offset] == 0) continue;
        
        for (int j = 0; j < k; j++) {
            if (counter[nums[i] + j + offset] == 0) return false;
            counter[nums[i] + j + offset]--;
        }
    }
    
    return true;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    int nums[MAX_NUMS];
    int numsSize = 0;
    
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    bool result = solution(nums, numsSize, k);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), processing takes O(n) with map operations

⚡ Linearithmic

Space Complexity

O(n)

Frequency map stores at most n distinct elements

⚡ Linearithmic Space

78.9K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort and Check Consecutive Sequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler