Problem Statement in English

You’re given an integer array nums and an integer k. A subarray is a contiguous part of an array. Return the number of good subarrays of nums.

A good array is an array where the number of different integers in that array is exactly k.

Approach

Calculating the number of subarrays with exactly k distinct integers can be done by calculating the number of subarrays with at least k distinct integers and subtracting the number of subarrays with at least k + 1 distinct integers.

In order to find the number of subarrays with at least k distinct integers, we can use a sliding window approach. We will maintain a hashmap to keep track of the frequency of elements in the current window. We will expand the right end of the window until we have at least k distinct integers, and then we will shrink the left end of the window while maintaining at least k distinct integers. Each time we have k distinct integers, we can count the number of subarrays that can be formed with the current window (total length of the array minus the right index).

And we’re done!

Solution in Python


class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        # atleast k - atleast (k + 1)
        N = len(nums)

        def atleast(n):
            l = res = 0
            hm = defaultdict(int)

            for r, v in enumerate(nums):
                hm[v] += 1

                while len(hm) == n:
                    res += N - r
                    
                    ol = nums[l]
                    hm[ol] -= 1
                    if not hm[ol]: del hm[ol]

                    l += 1

            return res

        return atleast(k) - atleast(k + 1)

Complexity

  • Time: $O(n)$
    Since we are using a sliding window approach, we are iterating through the array once, resulting in a time complexity of $O(n)$.

  • Space: $O(k)$
    Since we are using a hashmap to store the frequency of elements in the current window, the space complexity is $O(k)$ in the worst case when all elements are distinct.

Mistakes I Made

I had to look this up :(

And we are done.