Count the Number of Good Subarrays

Leetcode Problem:

• Count the Number of Good Subarrays

Summary

• This problem requires us to find the number of good subarrays in a given array
• A good subarray is a subarray that has at least k pairs of indices (i, j) such that i < j and arr[i] == arr[j].

Approach

• The solution uses a sliding window approach with two pointers, i and j, to traverse the array
• It also uses a hashmap to store the count of each element in the current window
• The time complexity of this approach is O(n), where n is the size of the array.

Complexity

• O(n)

Explanation

• The solution starts by initializing a hashmap to store the count of each element in the array
• It then traverses the array using two pointers, i and j
• For each element at index j, it increments the count of the element in the hashmap and subtracts 1 from the count of the element at index i
• If the count of the element at index j is greater than 0, it means that there is already a pair of indices (i, j) such that i < j and arr[i] == arr[j], so it increments the result by j
• If the count of the element at index j is 0, it means that there is no pair of indices (i, j) such that i < j and arr[i] == arr[j], so it increments the count of the element at index j and continues to the next element
• Finally, the solution returns the result.

Solution Code:

class Solution {
public:
    long long countGood(vector& A, int k) {
        long long res = 0;
        unordered_map count;
        for (int i = 0, j = 0; j < A.size(); ++j) {
            k -= count[A[j]]++;
            while (k <= 0)
                k += --count[A[i++]];
            res += i;
        }
        return res;
    }
};