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

Question

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

Please review for performance.

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;
 }
 }
}

• Gilad: I never get people who down vore without writing why
• Countingstuff: 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.
• Gilad: I think you are right. The sorting has no meaning here

Answer 1

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.