[Leetcode] 2537. Count the Number of Good Subarrays

https://leetcode.com/problems/count-the-number-of-good-subarrays/description/?envType=daily-question&envId=2025-04-16

initial

I tried calculating via n!, which calculates all possible permutation like

but we are not considering the subarrays. Like we depend on the iterating index to calculate but we need to make all possible combinations.

solution

Its very confusing but understand this maths first
1) to calculate all possible total number of all possible subarrays in an array of length n is n*(n+1)//2

The n*(n-1)//2 is calculating unique pairs by choosing 2.
For example, in an array [1, 2, 3, 4]:

Possible pairs: (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)
Total count: 6 pairs

In this case, we wanna calc all possible subarrays so we use top

2) since we are using top formula, which consits of single subarrays like [2], or [69], the invalid subarray count needs to count these cases too.

The formula is
invalidCnt = (right-left+1)
For example, if we have left = 2 and right = 5, then we're counting these invalid subarrays:

Subarray [2,3,4,5]
Subarray [3,4,5]
Subarray [4,5]
Subarray [5]

That's exactly right - left + 1 = 4 subarrays.

3) the possible pair counting starts like if there is 0 3s, its 0 pair. If there is 1 3s, its 1 pair (cuz we just said [3] is valid). If there is 2 3s, it is 3 pair (1+2). So we are adding the previous pair.

we can calculate this like this tricky way

        for right in range(length):
            num = nums[right]
            pair+=dic[num]
            dic[num]+=1

So the main logic of solution is we are gonna calc all possible pairs along the way and minus the invalid pairs at the end

class Solution:
    def countGood(self, nums, k: int) -> int:
        length = len(nums)
        invalidCount = 0
        left=0
        dic = defaultdict(int)
        pair=0

        for right in range(length):
            num = nums[right]
            pair+=dic[num]
            dic[num]+=1

            while left<=right and pair>=k:
                current_val = nums[left]
                pair -= (dic[current_val]-1)
                dic[current_val]-=1
                left += 1
            invalidCount+=(right-left+1)
        return length*(length+1)//2 - invalidCount

complexity

n time
n space worst case cuz if all unique elements, dictionary has to store n unique elements