Fixed-Size Window Target Counting

Problem Statement

Given an array of integers nums, a window size k, and a target value target, find the number of distinct elements that appear exactly k times within each moving window of size k.

Constraints

• 1 <= nums.length <= 10^5
• 1 <= k <= nums.length
• 0 <= nums[i] <= 10^5
• 0 <= target <= 10^5

Examples

1. Example 1: plaintext Input: nums = [1,1,1,1,1], k = 3, target = 1 Output: 1 Explanation: The sliding window of size 3 is [1,1,1], which contains exactly one distinct element '1' that appears exactly 3 times.

2. Example 2: `plaintext Input: nums = [1,2,3,2,2], k = 2, target = 2 Output: 2 Explanation: We have two windows of size 2:

   • [1,2] contains the elements '1' and '2', but '2' appears only once.
   • [2,3] contains the elements '2' and '3', but '2' appears only once.
   • [3,2] contains the elements '2' and '3', but '2' appears only once.
   • [2,2] contains the element '2' that appears exactly 2 times. `

Solution

To solve this problem, you can use a sliding window approach combined with a hash map to count the occurrences of each element within the window.

1. Initialize a hash map countMap to store the count of each element within the current window.
2. Initialize a variable result to store the number of distinct elements that appear exactly k times.
3. Iterate through the array nums with a sliding window of size k:
   • For each element in the window, update its count in countMap.
   • If an element's count becomes k, increment result if it's not the target value or if it's the target and its count was previously less than k.
   • If an element's count exceeds k, decrement result if it's not the target value or if it's the target and its count was previously exactly k.
4. Return the result.

Here's a sample implementation in Python:

`python def fixedSizeWindowTargetCount(nums, k, target): countMap = {} result = 0 for i in range(k): countMap[nums[i]] = 1 + countMap.get(nums[i], 0)

for i in range(k, len(nums)):
    if nums[i - k] != target:
        if countMap[nums[i - k]] == k:
            result -= 1
        countMap[nums[i - k]] -= 1
    else:
        if countMap[nums[i - k]] == k - 1:
            result += 1
        countMap[nums[i - k]] -= 1
    
    if nums[i] != target:
        if countMap.get(nums[i], 0) == k - 1:
            result += 1
        countMap[nums[i]] = 1 + countMap.get(nums[i], 0)
    else:
        if countMap.get(nums[i], 0) == k - 1:
            result += 1
        countMap[nums[i]] = 1 + countMap.get(nums[i], 0)

return result

`

This solution has a time complexity of O(n), where n is the length of the input array, and a space complexity of O(n) due to the hash map.