Subarrays With Exactly K Distinct Integers

You are given an array of n integers and an integer K. Your task is to determine the number of contiguous subarrays (i.e. segments) that contain exactly K distinct integers.

The solution can be derived using the formula:

\( f(K) = g(K) - g(K-1) \)

where \( g(K) \) denotes the number of subarrays with at most K distinct integers. An efficient solution uses a two-pointer (sliding window) approach to compute \( g(K) \) in \(O(n)\) time.

inputFormat

The first line of input contains two integers, n and K, where n is the number of elements in the array and K is the required number of distinct integers.

The next line contains n space-separated integers representing the array.

outputFormat

Output a single integer: the number of contiguous subarrays that contain exactly K distinct integers.

5 2
1 2 1 2 3

7