We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count the Number of Good Subarrays

Difficulty: Medium

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.

Key Insights

  • A subarray is defined by its start and end indices, and we need to count pairs of equal elements within it.
  • The number of pairs of equal elements can be derived from the frequency of each element in the subarray.
  • Using a hashmap (or dictionary) to track frequencies can help efficiently calculate the number of good subarrays.
  • A sliding window technique can be employed to expand and contract the subarray, while maintaining the counts of pairs.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use a two-pointer approach combined with a hashmap to count the frequency of elements in the current subarray. We will maintain a count of good pairs and expand the subarray until the count of pairs is at least k. If it's not, we will move the left pointer to contract the subarray. This ensures that we check every possible subarray efficiently.

Code Solutions

def countGoodSubarrays(nums, k):
    from collections import defaultdict
    
    left = 0
    count = 0
    pairs = 0
    freq = defaultdict(int)
    
    for right in range(len(nums)):
        freq[nums[right]] += 1
        pairs += freq[nums[right]] - 1  # Count new pairs formed with nums[right]
        
        while pairs >= k:
            count += len(nums) - right  # All subarrays from left to right are good
            freq[nums[left]] -= 1
            pairs -= freq[nums[left]]  # Remove pairs formed with nums[left]
            left += 1
            
    return count
← Back to All Questions