#2537

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count the Number of Good Subarrays

Count the number of subarrays that contain at least k pairs of equal elements using array scanning and hash lookup.

Problem Statement

Given an integer array nums and an integer k, return the number of good subarrays of nums. A subarray is considered 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 the array. The goal is to efficiently find and count these subarrays using a scanning technique that tracks element frequencies, using a sliding window approach.

Examples

Example 1

Input: nums = [1,1,1,1,1], k = 10

Output: 1

The only good subarray is the array nums itself.

Example 2

Input: nums = [3,1,4,3,2,2,4], k = 2

Output: 4

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

Solution Approach

Array Scanning with Hash Table

Traverse the array and for each element, track its frequency in a hash table. This allows for quick lookup of pairs of equal elements, which helps determine if the subarray meets the k-pair condition.

Sliding Window Technique

Use a sliding window to dynamically adjust the subarray under consideration. For a fixed left index, move the right index to find the smallest subarray where the number of pairs exceeds or equals k.

Efficient Pair Calculation

To calculate pairs efficiently, maintain the frequency of each number within the sliding window. This helps in quickly determining the number of pairs in the current window as it expands or contracts.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n) since we scan through the array once while updating the hash table. The space complexity is O(n) due to the hash table that stores element frequencies.

What Interviewers Usually Probe

Candidates who use sliding window efficiently demonstrate understanding of optimal subarray searching techniques.
Look for solutions that maintain a hash table to track element frequencies for fast lookup and pair counting.
The ability to adjust the sliding window while maintaining the correct number of pairs is crucial for an optimal solution.

Common Pitfalls or Variants

Common pitfalls

Not maintaining an efficient hash table can lead to a suboptimal solution.
Misunderstanding the sliding window approach can cause incorrect counting of valid subarrays.
Failing to properly adjust the window size when necessary can result in over-counting or under-counting subarrays.

Follow-up variants

Count the number of good subarrays with at least k pairs of equal elements, but with a modified constraint on array size.
Count good subarrays with exactly k pairs of equal elements, changing the requirement for the pair count.
Allow subarrays to be non-contiguous and count the pairs of equal elements in this modified scenario.

FAQ

How can I efficiently solve the "Count the Number of Good Subarrays" problem?

Use a sliding window approach with a hash table to keep track of element frequencies and efficiently count the pairs of equal elements in subarrays.

What is the optimal time complexity for "Count the Number of Good Subarrays"?

The optimal time complexity is O(n), where n is the length of the array, as you only need to scan the array once while maintaining a hash table.

How does the sliding window approach help in solving this problem?

The sliding window approach allows you to dynamically adjust the subarray size while maintaining a count of valid pairs, which helps in determining good subarrays efficiently.

What mistakes should I avoid in the "Count the Number of Good Subarrays" problem?

Avoid inefficient pair counting and ensure you are correctly adjusting the window size when necessary to count the valid subarrays correctly.

Can you explain the "array scanning plus hash lookup" pattern used in this problem?

This pattern involves scanning the array while using a hash table to quickly look up element frequencies and count pairs, which is crucial for determining valid subarrays.

terminal

Solution

Solution 1: Hash Table + Two Pointers

If a subarray contains $k$ pairs of identical elements, then this subarray must contain at least $k$ pairs of identical elements.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

Continue Practicing

#2461 maximum sum of distinct subarrays with length k #2653 sliding subarray beauty #2747 count zero request servers