1
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ I never get people who down vore without writing why \$\endgroup\$ – Gilad Mar 27 at 11:38
  • \$\begingroup\$ 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. \$\endgroup\$ – Countingstuff Mar 28 at 0:15
  • \$\begingroup\$ I think you are right. The sorting has no meaning here \$\endgroup\$ – Gilad Mar 28 at 6:55
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.