1296. Divide Array in Sets of K Consecutive Numbers

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 < = n u m s . l e n g t h < = 10 5 1 <= k <= nums.length <= 10^51<=k<=nums.length<=105
• 1 < = n u m s [ i ] < = 10 9 1 <= nums[i] <= 10^91<=nums[i]<=109

From: LeetCode
Link: 1296. Divide Array in Sets of K Consecutive Numbers

Solution:

Ideas:

Sort the array, then repeatedly start groups from the smallest number that still has remaining occurrences.

Code:

#include<stdbool.h>#include<stdlib.h>typedefstruct{intkey;intcount;bool used;}HashEntry;staticintcompare(constvoid*a,constvoid*b){intx=*(constint*)a;inty=*(constint*)b;return(x>y)-(x<y);}staticunsignedinthashValue(intkey,intsize){return((unsignedint)key*2654435761u)%size;}staticHashEntry*findEntry(HashEntry*table,intsize,intkey){unsignedintindex=hashValue(key,size);while(table[index].used&&table[index].key!=key){index=(index+1)%size;}return&table[index];}boolisPossibleDivide(int*nums,intnumsSize,intk){if(numsSize%k!=0){returnfalse;}qsort(nums,numsSize,sizeof(int),compare);inttableSize=numsSize*3+1;HashEntry*table=calloc(tableSize,sizeof(HashEntry));if(table==NULL){returnfalse;}/* Count each number. */for(inti=0;i<numsSize;i++){HashEntry*entry=findEntry(table,tableSize,nums[i]);if(!entry->used){entry->used=true;entry->key=nums[i];}entry->count++;}for(inti=0;i<numsSize;i++){HashEntry*startEntry=findEntry(table,tableSize,nums[i]);intgroups=startEntry->count;if(groups==0){continue;}/* Form 'groups' sets beginning with nums[i]. */for(intj=0;j<k;j++){HashEntry*entry=findEntry(table,tableSize,nums[i]+j);if(!entry->used||entry->count<groups){free(table);returnfalse;}entry->count-=groups;}}free(table);returntrue;}