<p>Given an array of integers <code>nums</code> and a positive integer <code>k</code>, check whether it is possible to divide this array into sets of <code>k</code> consecutive numbers.</p>

<p>Return <code>true</code> <em>if it is possible</em>.<strong> </strong>Otherwise, return <code>false</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,3,4,4,5,6], k = 4
<strong>Output:</strong> true
<strong>Explanation:</strong> Array can be divided into [1,2,3,4] and [3,4,5,6].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
<strong>Output:</strong> true
<strong>Explanation:</strong> Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].
</pre>

<p><strong class="example">Example 3:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

<p>&nbsp;</p>
<strong>Note:</strong> This question is the same as&nbsp;846:&nbsp;<a href="https://leetcode.com/problems/hand-of-straights/" target="_blank">https://leetcode.com/problems/hand-of-straights/</a>
class Solution:
    # Looking good but time limit exceeded on 43 out of 60
    def isPossibleDivide(self, nums: List[int], k: int) -> bool:
        # Hah so it's not just this.
        #return False if len(nums) % k else True
        if len(nums) % k:
            return False
        nums.sort()
        print(nums)
        batch_hooks = [-2, -2] # lower and higher attachment points of our batch
        extras = collections.defaultdict(int)
        def add_to_batch(val: int) -> None:
            nonlocal batch_hooks
            if batch_hooks[0] == -2: # No batch started yet
                batch_hooks = [val - 1, val + 1]
            elif val == batch_hooks[0]: # We're adding this to the lower end of the straight
                batch_hooks[0] -= 1
            else:
                batch_hooks[1] += 1
            # Check if this batch is done
            if batch_hooks[1] - batch_hooks[0] - 1 == k:
                batch_hooks = [-2, -2]
            return
        def add_from_extras() -> bool:
            did_add = False
            while extras:
                value_to_add = None
                for i in [0, 1]:
                    if batch_hooks[i] in extras:
                        value_to_add = batch_hooks[i]
                if value_to_add is None:
                    break
                did_add = True
                add_to_batch(value_to_add)
                if extras[value_to_add] == 1:
                    del extras[value_to_add]
                else:
                    extras[value_to_add] -= 1
                if batch_hooks[0] == -2: # We just completed a batch
                    break
            return did_add
        i = 0
        #nums = nums[:100] # nocommit
        while i < len(nums):
            #print(i, extras)
            if add_from_extras():
                continue
            if batch_hooks[0] == -2 or (nums[i] == batch_hooks[0] or nums[i] == batch_hooks[1]):
                add_to_batch(nums[i])
            else:
                extras[nums[i]] += 1
            i += 1
        #print(extras) # We're not even reaching here in the timeout test case 43.
        while extras and add_from_extras():
            pass
        return True if not extras else False
        
26000