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

from collections import Counter
class Solution:
    def countGood(self, nums: List[int], k: int) -> int:
        
        left = 0
        count_map = Counter()
        total_pairs_in_window = good_subarrays = 0
        
        """
        We iterate keeping a variable window. We keep count of each element. The moment it cross 1. We add 1 to the overall pair.. that is if there are 2 repeating
        items in a subarray, it'll conttribute to making 1 pair. 3 means 2 pair.. and then we update the counter map.
        
        Now till the point there's atleast k pairs, we shrink the window till the condition is not met. Meanwhile calculating all the good subarrays. 
        We do this per iteration by on counts for all subarrays starting from left, ending between right and whole array.
        Now we're moving the left forward, So in total how many the left identity contributed we subtractit. Each number contributes to n-1 pairs
        Then we move left forward. 
        Toward the end return total good subarrays!! 
        
        """
        
        for right in range(len(nums)):
            if nums[right] in count_map:
                total_pairs_in_window += count_map[nums[right]] # Each occurrence of nums[right] adds `count_map[nums[right]]` pairs
            
            count_map[nums[right]] += 1
            
            # if there's atleast k pairs in the window, we shrink the window till we reduce it. meanwhile calculating the good_subaaray counts 
            while total_pairs_in_window>=k:
                good_subarrays += len(nums)-right # counts for all subarrays starting from left, ending between right and whole array
                total_pairs_in_window -= count_map[nums[left]]-1 
                # Now we're moving the left forward, So in total how many the left identity contributed we subtractit. Each number contributes to n-1 pairs
                count_map[nums[left]] -= 1
                left += 1
            
        return good_subarrays

573