Count Subarrays with At Most K Distinct Integers

Given an integer array `arr` and an integer `k`, count the total number of contiguous subarrays that contain **at most `k` distinct** elements.

Input Format

arr = array of integers, k = limit of distinct values

Output Format

integer (number of subarrays with <= k distinct elements)

Constraints

  • 1 <= arr.length <= 10^5; 0 <= arr[i] <= 10^9; 0 <= k <= arr.length

Examples

Example 1:

Input:

arr = [1,2,2,3]
k = 2

Output:

9

Example 2:

Input:

arr = [1,2,1,3]
k = 2

Output:

8
Loading...
Count Subarrays with At Most K Distinct Integers