<p>You are given an integer array <code>nums</code> and an integer <code>threshold</code>.</p>

<p>Find any subarray of <code>nums</code> of length <code>k</code> such that <strong>every</strong> element in the subarray is <strong>greater</strong> than <code>threshold / k</code>.</p>

<p>Return<em> the <strong>size</strong> of <strong>any</strong> such subarray</em>. If there is no such subarray, return <code>-1</code>.</p>

<p>A <strong>subarray</strong> is a contiguous non-empty sequence of elements within an array.</p>

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

<pre>
<strong>Input:</strong> nums = [1,3,4,3,1], threshold = 6
<strong>Output:</strong> 3
<strong>Explanation:</strong> The subarray [3,4,3] has a size of 3, and every element is greater than 6 / 3 = 2.
Note that this is the only valid subarray.
</pre>

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

<pre>
<strong>Input:</strong> nums = [6,5,6,5,8], threshold = 7
<strong>Output:</strong> 1
<strong>Explanation:</strong> The subarray [8] has a size of 1, and 8 &gt; 7 / 1 = 7. So 1 is returned.
Note that the subarray [6,5] has a size of 2, and every element is greater than 7 / 2 = 3.5. 
Similarly, the subarrays [6,5,6], [6,5,6,5], [6,5,6,5,8] also satisfy the given conditions.
Therefore, 2, 3, 4, or 5 may also be returned.</pre>

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

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

class Solution:
    def validSubarraySize(self, nums: List[int], threshold: int) -> int:

        '''        
        the possible k's range from 1 to n. For each k, we can try to find subarrays such that they are all valid

        as k increases, the threshold for a number to be valid goes down

        so numbers that were valid for a smaller k, will remain valid

        that's why we need to merge subarrays with a disjoint set union (dsu)

        every time we activate a number, find the biggest valid subarray that it creates

        sort the numbers in desc order and map them to their indices

        for each k, move through the sorted numbers as much as we can until numbers stop being greater than the threshold
            merge intervals for each number wherever possible
        '''

        n = len(nums)

        dsu = [[num, i, i, i] for i, num in enumerate(nums)]
        idxToDsuEl = [dsu[i] for i in range(n)]
        
        dsu.sort(key=lambda el: -el[0])

        def merge(idxOfNum, threshold):
            dsuEl = idxToDsuEl[idxOfNum]
            _, _, leftOfSubArr, rightOfSubArr = dsuEl[0], dsuEl[1], dsuEl[2], dsuEl[3]

            # merge with i - 1, find
            if idxOfNum - 1 >= 0:
                dsuEl = idxToDsuEl[idxOfNum - 1]
                leftNum = dsuEl[0]

                if leftNum > threshold:
                    leftOfSubArr = min(leftOfSubArr, dsuEl[2])
                    rightOfSubArr = max(rightOfSubArr, dsuEl[3])
            
            # merge with i + 1, find rightmost
            if idxOfNum + 1 < n:
                dsuEl = idxToDsuEl[idxOfNum + 1]
                rightNum = dsuEl[0]

                if rightNum > threshold:
                    leftOfSubArr = min(leftOfSubArr, dsuEl[2])
                    rightOfSubArr = max(rightOfSubArr, dsuEl[3])

            idxToDsuEl[leftOfSubArr][2] = leftOfSubArr
            idxToDsuEl[leftOfSubArr][3] = rightOfSubArr
            idxToDsuEl[rightOfSubArr][2] = leftOfSubArr
            idxToDsuEl[rightOfSubArr][3] = rightOfSubArr

            return rightOfSubArr - leftOfSubArr + 1

        dsuPtr = 0

        for k in range(1, n + 1):
            if dsuPtr >= n:
                break

            activeThreshold = threshold / k

            while dsuPtr < n and dsu[dsuPtr][0] > activeThreshold:
                if merge(dsu[dsuPtr][1], activeThreshold) >= k:
                    return k
                
                dsuPtr += 1
                    
        return -1

40600