# LeetCode: Divide Array in Sets of K Consecutive Numbers C#

https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/

Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into sets of k consecutive numbers Return True if its 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 = [3,3,2,2,1,1], k = 3
Output: true

Example 4:

Input: nums = [1,2,3,4], k = 3
Output: false
Explanation: Each array should be divided in subarrays of size 3.

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= nums.length


using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace ArrayQuestions
{
/// <summary>
/// https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/
/// </summary>
[TestClass]
public class DivideArrayinSetsofKConsecutiveNumbersTest
{
[TestMethod]
public void TestExample()
{
int[] nums = {1, 2, 3, 3, 4, 4, 5, 6};
int k = 4;
Assert.IsTrue(DivideArrayinSetsofKConsecutiveNumbers.IsPossibleDivide(nums, k));
}

[TestMethod]
public void TestFailed()
{
int[] nums = { 1, 2, 3,4};
int k = 3;
Assert.IsFalse(DivideArrayinSetsofKConsecutiveNumbers.IsPossibleDivide(nums, k));
}
}

public class DivideArrayinSetsofKConsecutiveNumbers
{
public static bool IsPossibleDivide(int[] nums, int k)
{
if (nums.Length % k != 0)
{
return false;
}

var dict = new SortedDictionary<int, int>();
foreach (var num in nums)
{
if (!dict.TryGetValue(num, out var value))
{
value = dict[num] = 0;
}

dict[num] = value+1;
}

for (int i = 0; i < nums.Length / k; i++)
{
int start = dict.FirstOrDefault(x=>x.Value >0).Key;
dict[start]--;
for (int j = 1; j < k; j++)
{
if (!dict.ContainsKey(start + j) || dict[start + j] < 1)
{
return false;
}

dict[start + j]--;
}
}

return true;
}
}
}

• I never get people who down vore without writing why Mar 27 '20 at 11:38
• Not too familiar with c# but isn't the call to FirstOrDefault quite slow, like O(n) implying O(n^2)? I would suggest instead that you don't need a SortedDictionary, instead, just have a dictionary containing the counts, then sort the array and loop over that. That would be O(nlogn). I think there is an O(n) solution if you think about it, as actually I don't think you need to sort anything, simply make the dictionary of counts, start anywhere say at k, and go back until k-t isn't in the dictionary, then k-t+1 must be the start of a sequence, go up, then go back down again, etc. Mar 28 '20 at 0:15
• I think you are right. The sorting has no meaning here Mar 28 '20 at 6:55

Here's some C# in accordance with my first suggestion of sorting the array and looping.

public bool IsPossibleDivide(int[] nums, int k)
{
if (nums.Length % k != 0)
{
return false;
}

var dict = new Dictionary<int, int>();
foreach (var num in nums)
{
if (!dict.TryGetValue(num, out var value))
{
value = dict[num] = 0;
}

dict[num] = value+1;
}
Array.Sort(nums);

for (int i = 0; i < nums.Length; i++)
{
var currVal = nums[i];
if(dict[currVal] > 0)
{
for(int j = 0; j < k; j++)
{
if(!dict.ContainsKey(currVal + j))
{
return false;
}
dict[currVal + j]--;
}
}
}

return true;
}


This is significantly faster, and is O(nlogn), as I say I think there's a O(n) solution but I'm not really sure of the exact details and I don't know much C#, probably I could write it in JS if you like.

As I say, this

int start = dict.FirstOrDefault(x=>x.Value >0).Key;

looks bad to me because once you've done a good number of the consecutive numbers, it might start having to look through a lot of the dict.