<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>

class Solution:
    def countGood(self, nums: List[int], k: int) -> int:
        res, i = 0,0
        counts = {}
        pairs = 0

        # keep right window increasing
        for j in range(len(nums)):
            if nums[j] not in counts:
                counts[nums[j]]=1
            else:
                counts[nums[j]]+=1
            
            # keep track of all the good pairs made
            if counts[nums[j]]>=1:
                pairs=pairs + (counts[nums[j]]-1)

            # if the good pairs have exceeded the limit
            while pairs >= k:
                # reduce the count assuming we will remove the left most value
                counts[nums[i]]-=1
                
                if counts[nums[i]]>=1:
                    # fix pairs
                    pairs= pairs - counts[nums[i]]

                # increment of i
                i+=1
            
            # reduced to the point nums[i:j] is no longer a good subarray
            # so if original i is i1, then nums[i1:j] was a good array, but nums[i:j] is not a good array
            # meaning i:i2, each time we went down, we were still a good array, meaning till we go down to not a good array, we are
            # still a good array, so everything that was still a good array, was added
            res+=i


        return res

516