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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count the Number of Good Subarrays

Number: 2626

Difficulty: Medium

Paid? No

Companies: Uber, Amazon

Problem Description

Given an integer array nums and an integer k, a subarray is considered good if, within the subarray, there are at least k pairs of indices (i, j) with i < j such that nums[i] equals nums[j]. The task is to count the total number of good subarrays in nums.

Key Insights

  • Utilize a sliding window approach to keep track of a contiguous subarray.
  • Maintain a frequency map (hash table) to count the occurrences of each element in the window.
  • As you extend the window by moving the right pointer, update the number of pairs by adding the current frequency of the new element.
  • When the current window’s pair count reaches or exceeds k, every subarray that starts at the current left index and extends from the current right pointer to the end will also be good.
  • Shrink the window from the left while the condition holds to count all valid subarrays starting from earlier positions.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array, since each element is processed at most twice. Space Complexity: O(n), due to the space used by the frequency map.

Solution

We use a two-pointer (sliding window) strategy with a hash table to maintain the frequency count of elements in the current subarray and a variable to keep track of the number of matching pairs. When extending the window (by moving the right pointer), we update the pair count by adding the current frequency (since each occurrence already in the window forms a new pair with the added element). Once the window has k or more pairs, we know that any subarray starting at the current left pointer and ending anywhere from the current right pointer to the end of the array automatically satisfies the condition. We then slide the left pointer inward, updating the frequency map and reducing the pair count accordingly. This method ensures that all good subarrays are counted in linear time.

Code Solutions

def countGoodSubarrays(nums, k):
    # Initialize frequency dictionary, pointers, and counters.
    n = len(nums)
    freq = {}
    left = 0
    countPairs = 0
    result = 0

    # Iterate over the array with the right pointer.
    for right in range(n):
        x = nums[right]
        # Increase countPairs by the frequency of the current element seen so far.
        countPairs += freq.get(x, 0)
        freq[x] = freq.get(x, 0) + 1

        # While the current window has at least k pairs,
        # all subarrays from left to any index from right to end are good.
        while countPairs >= k and left <= right:
            result += (n - right)
            # Before moving left, adjust countPairs by reducing pairs formed with nums[left].
            freq_x = freq[nums[left]]
            countPairs -= (freq_x - 1)
            freq[nums[left]] -= 1
            left += 1

    return result

# Example usage:
print(countGoodSubarrays([3,1,4,3,2,2,4], 2))
← Back to All Questions