<p>Given an integer array <code>nums</code> and an integer <code>k</code>, return <em>the number of <strong>good</strong> subarrays of</em> <code>nums</code>.</p>

<p>A subarray <code>arr</code> is <strong>good</strong> if it there are <strong>at least </strong><code>k</code> pairs of indices <code>(i, j)</code> such that <code>i &lt; j</code> and <code>arr[i] == arr[j]</code>.</p>

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

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

<pre>
<strong>Input:</strong> nums = [1,1,1,1,1], k = 10
<strong>Output:</strong> 1
<strong>Explanation:</strong> The only good subarray is the array nums itself.
</pre>

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

<pre>
<strong>Input:</strong> nums = [3,1,4,3,2,2,4], k = 2
<strong>Output:</strong> 4
<strong>Explanation:</strong> There are 4 different good subarrays:
- [3,1,4,3,2,2] that has 2 pairs.
- [3,1,4,3,2,2,4] that has 3 pairs.
- [1,4,3,2,2,4] that has 2 pairs.
- [4,3,2,2,4] that has 2 pairs.
</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], k &lt;= 10<sup>9</sup></code></li>
</ul>

'''
We use sliding window to track the count of elements within the window
As the window expands we check how many pairs of indices satisfy the condition nums[i] == nums[j]
For each subarray (window) if the frequency of a number x is f we get the number of pairs formed by that number
And then for each window if the total number of pairs for all numbers in the window is at least k, we increment ans
Once the window is "good" we minimize/shrink the window by shrinking the left pointer but still ensuring window is good
'''
class Solution:
    def countGood(self, nums: List[int], k: int) -> int:
        frequency = defaultdict(int)
        left = 0
        pair_count = 0 # number of valid pairs in the current window
        good_subarrays = 0

        for right in range(len(nums)):
            frequency[nums[right]] += 1
            pair_count += frequency[nums[right]] - 1

            while pair_count >= k:
                # For each valid subarray, the number of good subarrays ending at 'right' is (right - left + 1) 
                # Since this window is already good, any larger subarray that ends beyond right will also be good. So, you add
                # len(nums) - right good subarrays in total (one for each potential end position from right to the end of the array).
                good_subarrays += len(nums) - right
                pair_count -= frequency[nums[left]] - 1
                frequency[nums[left]] -= 1
                left += 1
        return good_subarrays
518