LeetCode Weekly Contest Medium (Sliding Window) 2537. Count the Number of Good Subarrays
--
Count the Number of Good Subarrays
Given an integer array nums and an integer k, return the number of good subarrays of nums.
A subarray arr is good if it 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
Solution
Sliding Window
Intuitive Sliding Window O(n) Python Solution
Dry run some examples with sliding window technique.
Notice. You need to make sure the left most window, mid-window, and the right most window all collected. With the trend we found below:
Combine them to implement the solution.
class Solution:
def countGood(self, nums: List[int], k: int) -> int:
right = left = 0
window = defaultdict(int)
pairs_count = defaultdict(int)
ans = 0
while left < len(nums)-1:
# extend window
if right < len(nums):
window[nums[right]] += 1
if window[nums[right]] >= 2:
pairs_count[nums[right]] += window[nums[right]]-1
while sum([v for v in pairs_count.values()]) >= k:
ans += len(nums)-right if len(nums)-right else 1
# shrink window
window[nums[left]] -= 1
if window[nums[left]] >= 1:
pairs_count[nums[left]] -= window[nums[left]]
left += 1
continue
if right < len(nums):
right += 1
else:
left += 1
return ans
