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 &lt;= nums.length &lt;= 10^5
1 &lt;= nums[i] &lt;= 10^9
1 &lt;= k &lt;= nums.length



Please review for performance.

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

namespace ArrayQuestions
{
    /// &lt;summary&gt;
    /// https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/
    /// &lt;/summary&gt;
    [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&lt;int, int&gt;();
            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 &lt; nums.Length / k; i++)
            {
                int start = dict.FirstOrDefault(x=&gt;x.Value &gt;0).Key;
                dict[start]--;
                for (int j = 1; j &lt; k; j++)
                {
                    if (!dict.ContainsKey(start + j) || dict[start + j] &lt; 1)
                    {
                        return false;
                    }

                    dict[start + j]--;
                }
            }

            return true;
        }
    }
}
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&lt;int, int&gt;();
    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 &lt; nums.Length; i++)
    {
        var currVal = nums[i];
        if(dict[currVal] &gt; 0) 
        {
            for(int j = 0; j &lt; 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=&gt;x.Value &gt;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.