Hard

Subarrays with K Different Integers

LAB

Return the number of contiguous subarrays containing exactly k distinct integers.

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    2,
    1,
    2,
    3
  ],
  "k": 2
}

Output
7

FUNCTION SHAPE

nums: intArrayk: int→int

SOLUTION NOTE

This is a hard problem. But it seems so easy right? This is the power of templates and thinking through patterns.

Reveal reference solution +

pythonREFERENCE

def subarraysWithKDistinct(self, s: List[int], k: int) -> int:
    def atMostK(k: int) -> int:
        n = len(s)
        freq = Counter()
        l = 0
        res = 0

        for r in range(n):
            freq[s[r]] += 1
            while len(freq) == k + 1:
                freq[s[l]] -= 1
                if freq[s[l]] == 0:
                    del freq[s[l]]
                l += 1
            res += r - l + 1

        return res

    return atMostK(k) - atMostK(k - 1)

TimeO(n)

SpaceO(k)

Open on LeetCode ↗