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