Count Subarrays with Bounded Frequencies
In data processing pipelines, it's often crucial to identify segments of data that adhere to specific statistical properties. For instance, ensuring no single data point overwhelms a sample can prevent bias or system instability. This problem challenges you to count all contiguous segments (subarrays) within a larger dataset where every unique element appears a limited number of times, reflecting a common constraint in various analytical and sampling tasks.
You are tasked with implementing a function that takes an array of integers nums and an integer k. Your function should return the total count of all subarrays [L, R] (where 0 <= L <= R < nums.length) such that for every distinct integer x present in nums[L...R], its frequency within that specific subarray nums[L...R] is at most k.
Function Signature:
function countBoundedFrequencySubarrays(nums: number[], k: number): number
function countBoundedFrequencySubarrays(nums, k)
Input:
nums: An array of integers. Represents the main dataset.k: An integer. Represents the maximum allowed frequency for any single element within a valid subarray.Output:
k applies to each distinct element within a given subarray. For example, if k=1 and a subarray is [1, 2, 1], it is invalid because 1 appears twice.nums can contain duplicate values.nums is empty, the count of subarrays is 0.Examples
Example 1
Input:
nums = [1, 2, 1, 2, 3], k = 1
Output:
10
Note:
For [1,2,1,2,3] with k=1: right=0, window=[1], count+=1. right=1, window=[1,2], count+=2. right=2, window becomes [2,1] after shrinking, count+=2. right=3, window becomes [1,2] after shrinking, count+=2. right=4, window=[1,2,3], count+=3. Total = 1+2+2+2+3 = 10.
Example 2
Input:
nums = [1, 1, 1, 2, 2], k = 1
Output:
6
Note:
For [1,1,1,2,2] with k=1: right=0, window=[1], count+=1. right=1, window becomes [1] after shrinking, count+=1. right=2, window becomes [1] after shrinking, count+=1. right=3, window=[1,2], count+=2. right=4, window becomes [2] after shrinking multiple times, count+=1. Total = 1+1+1+2+1 = 6.
Example 3
Input:
nums = [1, 2, 3], k = 1
Output:
6
Note:
All subarrays are valid since k=1 allows each element once: [1], [2], [3], [1,2], [2,3], [1,2,3]. The total count is N*(N+1)/2 = 3*(3+1)/2 = 6.
Constraints
1 <= nums.length <= 10^51 <= k <= 10^51 <= nums[i] <= 10^9k is very restrictive or very permissive.Loading editor...