LeetCode Weekly Contest Medium (Sliding Window) 2537. Count the Number of Good Subarrays

2023-01-15 301 words 2 minutes

Contents

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 <= 105
1 <= nums[i], k <= 109

Solution

Sliding Window

Intuitive Sliding Window O(n) Python Solution

Dry run some examples with sliding window technique.

/blog/posts/2023/leetcode-weekly-contest-medium-sliding-window-2537.-count-the-number-of-good-subarrays/draft.jpg — Dry Run

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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