Count the Number of Good Subarrays - Solution & Explanation
Problem Statement
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 <= 109
Approach Overview
Problem 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 1: Use Sliding Window and Hash Map
This approach employs a sliding window technique along with a hash map to efficiently count the pairs in any subarray. The idea is to expand the window by moving the right pointer and add elements to the hash map until enough pairs are formed. If the number of pairs is at least k, increment the count of valid subarrays and shrink the window from the left to try shorter subarrays. This method effectively narrows down the potential subarrays without the need to explicitly check each one.
This Python code initializes a sliding window using two pointers, 'left' and 'right'. A hash map tracks the frequency of numbers within the window. As we extend the 'right' pointer, the current number contributes to the count of pairs if it was already encountered within the window. We then check if the number of pairs meets or exceeds k, and try to increment the 'good_subarrays' by attempting to shrink the window from the left.
Complexity
Time Complexity: O(n), where n is the length of the array, since each element is processed at most twice (once when 'right' pointer expands and once when 'left' pointer contracts).
Space Complexity: O(m), where m is the number of unique elements in the array due to the hash map.
Approach 2: Use Prefix Sum and Pair Counting
Another efficient approach involves using prefix sums and a map to account for pairs of elements. By prefixing the occurrence of numbers and counting pairs, you can dynamically build the count of valid pairs as you iterate through the array. This method relies on recognizing repeat occurrences as part of its summation process.
This C++ solution uses an unordered_map to track the frequency of elements appearing in the subarray defined by the sliding window margin from left to right. With each iteration of the right index, the count of pairs is updated if the same element appears before this position. When the counter for pairs meets or beats k, the current and succeeding elements form valid subarrays. The solution is efficient because it shifts focus from checks to counters.
Code
C++
JavaScript
Complexity
Time Complexity: O(n), where n is the number of elements in nums. The sliding window advances and retracts strategically limiting unnecessary iterations.
Space Complexity: O(m), requiring a hashmap to only remember prevalent elements at any time during the loop's execution.
Approach 3: 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.
We use a hash table cnt to count the occurrences of elements within the sliding window, a variable cur to count the number of identical pairs within the window, and a pointer i to maintain the left boundary of the window.
As we iterate through the array nums, we treat the current element x as the right boundary of the window. The number of identical pairs in the window increases by cnt[x], and we increment the count of x by 1, i.e., cnt[x] \leftarrow cnt[x] + 1. Next, we repeatedly check if the number of identical pairs in the window is greater than or equal to k after removing the leftmost element. If it is, we decrement the count of the leftmost element, i.e., cnt[nums[i]] \leftarrow cnt[nums[i]] - 1, reduce the number of identical pairs in the window by cnt[nums[i]], i.e., cur \leftarrow cur - cnt[nums[i]], and move the left boundary to the right, i.e., i \leftarrow i + 1. At this point, all elements to the left of and including the left boundary can serve as the left boundary for the current right boundary, so we add i + 1 to the answer.
Finally, we return the answer.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Use Sliding Window and Hash Map | Time Complexity: O(n), where n is the length of the array, since each element is processed at most twice (once when 'right' pointer expands and once when 'left' pointer contracts). Space Complexity: O(m), where m is the number of unique elements in the array due to the hash map. |
| Use Prefix Sum and Pair Counting | Time Complexity: O(n), where n is the number of elements in nums. The sliding window advances and retracts strategically limiting unnecessary iterations. Space Complexity: O(m), requiring a hashmap to only remember prevalent elements at any time during the loop's execution. |
| Hash Table + Two Pointers | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Count the Number of Good Subarrays | Thought Process | Khandani Template | Leetcode 2537 | MIK • codestorywithMIK • 14,213 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count the Number of Good Subarrays easy or hard?
Count the Number of Good Subarrays Python/Java solution
How to solve Count the Number of Good Subarrays in O(n)?
What is the best approach for Count the Number of Good Subarrays?
Is Count the Number of Good Subarrays asked at Google/Amazon/Meta?
What data structure is used in Count the Number of Good Subarrays?
What is the time complexity of Count the Number of Good Subarrays?
Ready to solve this problem?
Practice Count the Number of Good Subarrays with our built-in code editor and test cases.
Practice on FleetCode