Problem Informations

• Problem Index: 2537
• Problem Link: Count the Number of Good Subarrays
• Topics: Array, Hash Table, Sliding Window

Problem Description

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 \leq nums.length \leq 10^5$
• $1 \leq nums[i], k \leq 10^9$

Intuition

The problem requires us to determine the number of contiguous subarrays for which there are at least k pairs of indices (i, j) such that i < j and arr[i] == arr[j]. This implies that we need to find subarrays with a certain level of repetition. The focus is to efficiently track the number of such pairs within subarrays in order to ascertain when a subarray becomes “good”. We recognize that as the length of the subarray increases, the number of pairs can only increase or stay the same due to more elements potentially repeating.

Approach

We employ a two-pointer or sliding window technique combined with a frequency hashmap to track occurrences of elements and efficiently count pairs within the current window.

1. Initialize Required Variables:

   • ans, to store the total count of good subarrays, is initialized to zero.
   • currentPairs, to record the number of pairs within the current window, is initialized to zero.
   • frequency, an unordered hashmap, maps each element to its frequency in the current window.
   • left, the starting index of the window, is initialized to 0.

2. Expand the Window:

   • Traverse the array using right as the endpoint of the current window.
   • For each element nums[right], update currentPairs by adding the frequency of nums[right] from the hashmap. This is because each occurrence of nums[right] creates additional pairs with all its previous occurrences within the window.
   • Increment the frequency of nums[right] in the hashmap.

3. Check and Contract the Window:

   • While the number of pairs currentPairs is greater than or equal to k and the left pointer is less than or equal to right, execute the inner loop:
     • Every subarray that starts from left and ends anywhere from right to n-1 is good because they satisfy the pair requirement.
     • Therefore, increment ans by (n - right) which represents all such valid subarrays.
     • To explore other potential good subarrays, reduce the window size by moving left to the right:
       • Decrement the frequency of nums[left] in the hashmap.
       • Reduce currentPairs by the new frequency of nums[left], since removing an element affects the pairing count.
       • Increment left to incrementally reduce the window size.

4. Return the Result:

   • After the loop completes, ans contains the total number of good subarrays that satisfy the condition throughout the entire array.

This approach efficiently traverses the nums array once, making pair counts and subarray evaluations with an overall linear complexity relative to the size of the array. This ensures performance is optimal even with larger input sizes up to the constraint limits.

Code

C++

class Solution {
public:
    long long countGood(vector<int>& nums, int k) {
        long long ans = 0;
        long long currentPairs = 0;
        unordered_map<int, long long> frequency;
        int left = 0;
        int n = nums.size();
        
        for (int right = 0; right < n; ++right) {
            // Each time we add nums[right], it forms new pairs with its previous occurrences.
            currentPairs += frequency[nums[right]];
            frequency[nums[right]]++;
            
            // If current window [left, right] contains at least k pairs,
            // every subarray starting at left and ending from right to n-1 will be "good".
            while (currentPairs >= k && left <= right) {
                // All subarrays starting from `left` to `right` with this `right` are valid.
                ans += (n - right);
                
                // Remove nums[left] from the current window, reducing pair count.
                frequency[nums[left]]--;
                currentPairs -= frequency[nums[left]];
                ++left;
            }
        }
        
        return ans;
    }
};

Python

class Solution:
    def countGood(self, nums, k):
        ans = 0
        currentPairs = 0
        frequency = {}
        left = 0
        n = len(nums)
        
        for right in range(n):
            # Each time we add nums[right], it forms new pairs with its previous occurrences.
            currentPairs += frequency.get(nums[right], 0)
            frequency[nums[right]] = frequency.get(nums[right], 0) + 1
            
            # If current window [left, right] contains at least k pairs,
            # every subarray starting at left and ending from right to n-1 will be "good".
            while currentPairs >= k and left <= right:
                # All subarrays starting from `left` to `right` with this `right` are valid.
                ans += (n - right)
                
                # Remove nums[left] from the current window, reducing pair count.
                frequency[nums[left]] -= 1
                currentPairs -= frequency[nums[left]]
                left += 1
        
        return ans

Complexity

• Time complexity: $O(n)$
  The time complexity is $O(n)$ because we are using a two-pointer technique, or sliding window approach, which involves iterating through the nums array with both right and left pointers. For each right pointer position, the left pointer only moves forward, ensuring that each element in nums is processed a constant number of times.

  Specifically, the outer for-loop iterates through the array with the right pointer, and within this loop, the left pointer controls the window size to ensure the number of good pairs is checked efficiently. The inner while-loop iterates without resetting the left pointer backward, therefore maintaining a linear traversal of elements, ensuring an overall time complexity of $O(n)$.

• Space complexity: $O(n)$
  The space complexity is $O(n)$ because we utilize an unordered map (frequency) to store the count of each element within the current window. In the worst-case scenario, all elements in nums are distinct, resulting in the map storing n elements. Hence, the required space grows linearly with respect to the input size.