Count the Number of Good Subarrays
The key idea
A subarray is 'good' when the total count of equal pairs reaches k; sliding window plus hash map to track element frequencies and current pair count lets you expand/shrink the window and count valid subarrays in O(n).
Problem
You are given an integer array nums and an integer k. A subarray is called good if the number of equal pairs (i, j) where i < j and both indices lie inside the subarray and have the same value is at least k. Return the number of good subarrays.
Two indices i and j (i < j) form an equal pair if nums[i] == nums[j].
Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9
- 1 <= k <= 10^9
Examples
Input: nums = [1,1,1,1,1], k = 10
Output: 1
Input: nums = [3,1,4,3,2,2,4], k = 2
Output: 4
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Sliding Window problems
- Find All Anagrams in a StringMEDIUM
- Longest Continuous Increasing SubsequenceEASY
- Longest Repeating Character ReplacementMEDIUM
- Longest Subarray of 1's After Deleting One ElementMEDIUM
- Longest Substring Without Repeating CharactersMEDIUM
- Max Consecutive Ones IIIMEDIUM
- Maximum Average Subarray IEASY
- Maximum Number of Vowels in a Substring of Given LengthMEDIUM
- Minimum Size Subarray SumMEDIUM
- Minimum Window SubstringHARD
- Permutation in StringMEDIUM
- Sliding Window MaximumHARD