Watch 10 video solutions for Count the Number of Good Subarrays, a medium level problem involving Array, Hash Table, Sliding Window. This walkthrough by codestorywithMIK has 13,465 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= nums.length <= 1051 <= nums[i], k <= 109Problem Overview: You are given an integer array nums and an integer k. A subarray is considered good if it contains at least k pairs of equal elements (i, j) where i < j and nums[i] == nums[j]. The task is to count how many subarrays satisfy this condition.
Approach 1: Sliding Window with Hash Map (O(n) time, O(n) space)
This approach uses a classic sliding window combined with a frequency map from a hash table. As the right pointer expands the window, update the frequency of the current number and increase the running pair count by the number of times that value has already appeared in the window. Once the pair count becomes at least k, every extension of the window to the right will still remain valid. Move the left pointer forward while maintaining the pair count, and add n - right valid subarrays each time the window satisfies the condition. This method works because pair counts update incrementally when elements enter or leave the window.
The key insight: when a value with frequency f enters the window, it creates f new equal pairs. When it leaves, those pairs disappear. Maintaining this count dynamically allows you to avoid recomputing combinations for every subarray.
Approach 2: Prefix Pair Counting (O(n log n) time, O(n) space)
This method tracks the cumulative number of equal pairs seen while iterating through the array. Maintain a frequency map for values and compute how many pairs each new element contributes to a running prefix pair total. For each position, determine how many earlier positions can form a subarray whose pair difference is at least k. This can be done by storing prefix values and using binary search or two-pointer techniques to count valid starting indices.
The idea treats the pair count like a prefix sum: the number of pairs in subarray [l, r] equals prefix[r] - prefix[l]. Finding subarrays with at least k pairs becomes a search problem over the prefix array. While not as elegant as the sliding window solution, it helps build intuition around pair accumulation and prefix-based counting.
Recommended for interviews: The sliding window + hash map solution is the expected answer. It runs in linear time and demonstrates strong control of two-pointer techniques and dynamic counting. Mentioning the prefix pair-counting idea shows understanding of how pair contributions accumulate, but the O(n) sliding window approach is what interviewers typically look for in medium-level array problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window + Hash Map | O(n) | O(n) | Best general solution; optimal for large arrays and typical interview scenarios |
| Prefix Pair Counting | O(n log n) | O(n) | Useful for understanding cumulative pair contributions or when adapting prefix-based techniques |