# Count the Number of Good Subarrays
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-the-number-of-good-subarrays)
Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-good-subarrays
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array, Hash Table
---
## Problem
Given an integer array `nums` and an integer `k`, return _the number of **good** subarrays of_ `nums`.

A subarray `arr` is **good** if there are **at least** `k` pairs of indices `(i, j)` such that `i < j` and `arr[i] == arr[j]`.

A **subarray** is a contiguous **non-empty** sequence of elements within an array.

**Example 1:**

**Input:** nums = [1,1,1,1,1], k = 10
**Output:** 1
**Explanation:** The only good subarray is the array nums itself.

**Example 2:**

**Input:** nums = [3,1,4,3,2,2,4], k = 2
**Output:** 4
**Explanation:** 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.

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i], k <= 109`

# Approaches
## Brute Force with Optimization
This approach involves checking every possible contiguous subarray of `nums`. For each subarray, we calculate the number of pairs `(i, j)` where `i < j` and `nums[i] == nums[j]`. If this count is at least `k`, we increment our result. To avoid recomputing the pair count from scratch for every subarray, we can optimize it by fixing the start of the subarray and extending the end one element at a time, updating the pair count incrementally.
**Time:** O(N^2), where N is the number of elements in the input array. The two nested loops iterate through all `N * (N + 1) / 2` subarrays, and the operations inside the inner loop take constant time on average. · **Space:** O(N), where N is the number of elements in the input array. In the worst-case scenario, the frequency map for a subarray can store up to N distinct elements.
**Pros:** Simple and straightforward to understand and implement.; Correctly solves the problem for smaller input sizes.
**Cons:** The `O(n^2)` time complexity is too slow for the given constraints (`n` up to 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
We use two nested loops to generate all subarrays. The outer loop with index `i` determines the start of the subarray, and the inner loop with index `j` determines the end. For each starting index `i`, we initialize a hash map to store element frequencies and a variable `currentPairs` to count the pairs for subarrays starting at `i`.

As we iterate with `j` from `i` to the end of the array, we consider the element `nums[j]`. The number of new pairs this element forms is equal to its current frequency in the subarray `nums[i...j-1]`. We add this number to `currentPairs` and then update the frequency of `nums[j]` in the map. If at any point `currentPairs` becomes greater than or equal to `k`, we've found a good subarray `nums[i...j]`, and we increment our total count of good subarrays.

```java
class Solution {
    public long countGood(int[] nums, int k) {
        long goodSubarraysCount = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            java.util.Map<Integer, Integer> frequencyMap = new java.util.HashMap<>();
            long currentPairs = 0;
            for (int j = i; j < n; j++) {
                int num = nums[j];
                int freq = frequencyMap.getOrDefault(num, 0);
                currentPairs += freq;
                frequencyMap.put(num, freq + 1);
                if (currentPairs >= k) {
                    goodSubarraysCount++;
                }
            }
        }
        return goodSubarraysCount;
    }
}
```
### Algorithm
- Initialize a counter for good subarrays, `count`, to 0.
- Iterate through the array with a pointer `i` from `0` to `n-1` to select the starting element of a subarray.
- For each `i`, start a nested loop with a pointer `j` from `i` to `n-1` to select the ending element of the subarray.
- For each subarray `nums[i...j]`, maintain a frequency map and a running count of pairs, `currentPairs`.
- As the inner loop for `j` progresses, update the frequency of `nums[j]` and recalculate `currentPairs`.
- The number of new pairs added by `nums[j]` is equal to its frequency in `nums[i...j-1]`.
- If `currentPairs` is greater than or equal to `k`, it means `nums[i...j]` is a good subarray, so increment `count`.
- After both loops complete, return the total `count`.

## Sliding Window
A much more efficient solution uses the sliding window technique. The core idea relies on a monotonic property: if a subarray is 'good' (has at least `k` pairs), any subarray that contains it is also 'good'. This allows us to efficiently count subarrays without checking each one individually.

We maintain a window `[left, right]` and expand it by moving `right`. Once the window becomes 'good', we know that all subarrays starting at `left` and ending at or after `right` are also good. We add the count of these subarrays to our total and then shrink the window from the `left` to find the next minimal good subarray.
**Time:** O(N), where N is the number of elements in the input array. Both the `left` and `right` pointers traverse the array at most once, leading to a linear time complexity. · **Space:** O(N) in the worst case, where N is the number of elements. The space is used by the hash map to store frequencies of elements in the current window. If the number of distinct elements is `D`, the space complexity is `O(D)`.
**Pros:** Optimal time complexity, making it very efficient for large inputs.; Processes each element a constant number of times.
**Cons:** Requires careful handling of window shrinking and pair count updates.; Uses extra space for the frequency map, which could be large if there are many distinct numbers.
### Explanation
This approach uses two pointers, `left` and `right`, to define a sliding window. We also maintain a hash map for element frequencies and a `long` variable `currentPairs` for the number of pairs within the window.

The `right` pointer iterates from the beginning to the end of the array, expanding the window. For each element `nums[right]` added, we update `currentPairs`. The number of new pairs created is equal to the frequency of `nums[right]` *before* it was added. 

Once `currentPairs` reaches `k`, we've found a good subarray `nums[left...right]`. Any subarray that starts at `left` and ends at `right` or a later index will also be good. The number of such subarrays is `n - right`. We add this to our total `count`. 

Having counted all good subarrays starting at `left`, we can shrink the window by moving `left` one step to the right. When removing `nums[left]`, we update the frequency map and `currentPairs`. We continue shrinking the window as long as it remains good, adding `n - right` to the count at each step. This process ensures that each good subarray is counted exactly once.

```java
class Solution {
    public long countGood(int[] nums, int k) {
        long count = 0;
        int left = 0;
        long currentPairs = 0;
        java.util.Map<Integer, Integer> frequencyMap = new java.util.HashMap<>();
        int n = nums.length;

        for (int right = 0; right < n; right++) {
            int num = nums[right];
            currentPairs += frequencyMap.getOrDefault(num, 0);
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);

            while (currentPairs >= k) {
                count += (n - right);
                
                int leftNum = nums[left];
                frequencyMap.put(leftNum, frequencyMap.get(leftNum) - 1);
                currentPairs -= frequencyMap.get(leftNum);
                left++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize `count = 0`, `left = 0`, `currentPairs = 0`, and an empty `frequencyMap`.
- Iterate through the array with a `right` pointer from `0` to `n-1`.
- In each iteration, add `nums[right]` to the current window. Update `currentPairs` by adding the old frequency of `nums[right]`. Then, increment its frequency in the map.
- After expanding the window, check if `currentPairs >= k`. 
- If it is, it means the subarray `nums[left...right]` is good. Consequently, any subarray starting at `left` and ending at `right` or later (i.e., `nums[left...right]`, `nums[left...right+1]`, ..., `nums[left...n-1]`) is also good. There are `n - right` such subarrays. Add `n - right` to `count`.
- Now, shrink the window from the left by incrementing `left`. Remove `nums[left]` from the window by updating its frequency and `currentPairs`. The number of pairs lost is the new frequency of `nums[left]`.
- Repeat the shrinking step as long as `currentPairs` remains `>= k`.
- Continue iterating with the `right` pointer until the end of the array.
- Return `count`.

# Solutions
### Java

```java
class Solution {
public
  long countGood(int[] nums, int k) {
    Map<Integer, Integer> cnt = new HashMap<>();
    long ans = 0, cur = 0;
    int i = 0;
    for (int x : nums) {
      cur += cnt.getOrDefault(x, 0);
      cnt.merge(x, 1, Integer : : sum);
      while (cur - cnt.get(nums[i]) + 1 >= k) {
        cur -= cnt.merge(nums[i++], -1, Integer : : sum);
      }
      if (cur >= k) {
        ans += i + 1;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long countGood(vector<int> &nums, int k) {
    unordered_map<int, int> cnt;
    long long ans = 0;
    long long cur = 0;
    int i = 0;
    for (int &x : nums) {
      cur += cnt[x]++;
      while (cur - cnt[nums[i]] + 1 >= k) {
        cur -= --cnt[nums[i++]];
      }
      if (cur >= k) {
        ans += i + 1;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countGood(self, nums: List[int], k: int) -> int: cnt = Counter() ans = cur = 0 i = 0 for x in nums: cur += cnt[x] cnt[x] += 1 while cur - cnt[nums[i]] + 1 >= k: cnt[nums[i]] -= 1 cur -= cnt[nums[i]] i += 1 if cur >= k: ans += i + 1 return ans

```