<p>You are given an integer array <code>nums</code> and a <strong>positive</strong> integer <code>k</code>.</p>

<p>Return <em>the number of subarrays where the <strong>maximum</strong> element of </em><code>nums</code><em> appears <strong>at least</strong> </em><code>k</code><em> times in that subarray.</em></p>

<p>A <strong>subarray</strong> is a contiguous 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,2,3,3], k = 2
<strong>Output:</strong> 6
<strong>Explanation:</strong> The subarrays that contain the element 3 at least 2 times are: [1,3,2,3], [1,3,2,3,3], [3,2,3], [3,2,3,3], [2,3,3] and [3,3].
</pre>

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

<pre>
<strong>Input:</strong> nums = [1,4,2,1], k = 3
<strong>Output:</strong> 0
<strong>Explanation:</strong> No subarray contains the element 4 at least 3 times.
</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] &lt;= 10<sup>6</sup></code></li>
	<li><code>1 &lt;= k &lt;= 10<sup>5</sup></code></li>
</ul>

from collections import defaultdict
class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        #find max element in nums
        max_element = max(nums)

        #hash map to determine count of max element
        count_map = defaultdict(int)
        for i in nums:
            count_map[i]+=1

        # if count less than k return 0
        if count_map[max_element] < k:
            return 0

        # start with window size of k
        l = 0
        r = k-1

        #get starting count
        count_map = defaultdict(int)
        for i in nums[:k]:
            count_map[i]+=1

        cur_count = count_map[max_element]
        

        #continue until right >= len(nums)
        res = 0
        n= len(nums)
        while l == 0 or r < n:
            #print(l,r,res,cur_count)
        # if cur window contains k add it and anything after it increment left update cur count
            if cur_count == k:
                res+=1
                if n-1 - r > 0:
                    res+= n-1-r
            
                if nums[l] == max_element:
                    cur_count-=1
                l+=1
            
            # else increment right
            else:
                r+=1
                if r < n:
                    if nums[r] == max_element:
                        cur_count+=1
        return res








996