Frontend School

Count Subarrays with Bounded Frequencies

DSA
medium

Count Subarrays with Bounded Frequencies

Medium
Arrays
Hashing
Sliding Window

Overview

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.

What you need to do / Task

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.

Input & output

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:

  • A single integer: The total number of valid subarrays meeting the frequency constraint.

Clarifications

  • An empty subarray is not considered. Subarrays must have at least one element.
  • The frequency constraint 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.
  • If nums is empty, the count of subarrays is 0.

Examples

1

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.

2

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.

3

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

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • 1 <= k <= 10^5
  • 1 <= nums[i] <= 10^9
  • The solution should aim for optimal time complexity, ideally linear (O(N)), and space complexity (O(D) where D is the number of distinct elements).

What interviewers evaluate

  • Algorithmic Correctness: The solution must correctly count all valid subarrays under the given frequency constraint.
  • Efficiency: The approach should be optimized for time and space complexity, demonstrating an understanding of efficient data structures and algorithms (e.g., sliding window, hash maps).
  • Code Quality: Clarity, readability, and maintainability of the code, including proper variable naming and logical structure.
  • Edge Case Handling: Correctly handles edge cases such as single-element arrays, arrays with all identical elements, or arrays where k is very restrictive or very permissive.

Loading editor...