Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A value appearing f times in a window contributes f*(f - 1)/2 equal-value index pairs. Extending a window cannot remove pairs. Once a start position reaches at least k pairs, every later ending position also forms a good subarray with that start.

Approach

Maintain window frequencies and the total pair count. When adding or removing a value, replace its old pair contribution with its new one. After extending right, while the window has at least k pairs, add n - right for all valid endings of the current left boundary, then remove that leftmost value and advance left. Each start is counted once, at its earliest qualifying end. Return the total.

class Solution:
    def countGood(self, nums: List[int], k: int) -> int:
        n = len(nums)
        seen = defaultdict(int)
        res = 0

        def nC2(n):
            if n < 2:
                return 0
            return n * (n - 1) // 2

        pairs = 0
        left = 0

        for right in range(n):
            pairs -= nC2(seen[nums[right]])
            seen[nums[right]] += 1
            pairs += nC2(seen[nums[right]])
            while pairs >= k:
                res += n - right
                pairs -= nC2(seen[nums[left]])
                seen[nums[left]] -= 1
                pairs += nC2(seen[nums[left]])
                left += 1

        return res

Complexity analysis

Let n = nums.length and u be the number of distinct values. Time: O(n), because both sliding-window pointers advance monotonically. Auxiliary space: O(u) for frequencies.