Frontend School

Longest Subarray with Bounded Distinct Frequencies

DSA
hard

Longest Subarray with Bounded Distinct Frequencies

Hard
Arrays
Hashing
Sliding Window

Overview

In data analysis, understanding the distribution of values within a contiguous segment of data is crucial. This problem challenges you to find the longest subarray where the diversity of element frequencies is constrained. Specifically, you're looking for a segment where the number of unique frequencies observed among its elements does not exceed a given threshold k. This task is representative of scenarios requiring efficient windowed aggregations and frequency analysis on large datasets.

What you need to do / Task

Implement the function longestSubarrayWithBoundedDistinctFrequencies that takes an integer array nums and an integer k as input. Your function should return the length of the longest subarray [L, R] (inclusive) such that the number of distinct frequencies of elements within nums[L...R] is at most k.

Deliverables:

  1. Implement the longestSubarrayWithBoundedDistinctFrequencies function.
  2. The solution must be efficient enough to handle large inputs within typical time limits (e.g., O(N) or O(N log N)).

Input & output

Function Signature:

function longestSubarrayWithBoundedDistinctFrequencies(nums: number[], k: number): number
  • nums: An array of integers.
  • k: An integer representing the maximum allowed number of distinct frequencies.

Return Value:

  • A single integer representing the length of the longest balanced subarray. If nums is empty, or if no valid subarray of length >= 1 exists (e.g., for k=0 and a non-empty nums array), return 0.

Clarifications

  • For an empty subarray, there are 0 distinct frequencies. However, the problem asks for the length of the longest non-empty subarray. If nums is empty, the result is 0.
  • If k=0, no non-empty subarray can be valid, as any element in a subarray will have a frequency of at least 1, leading to at least one distinct frequency. In this case, the function should return 0 for a non-empty nums array.
  • nums[i] can be large, requiring the use of hash maps for frequency counting.

Examples

1

Example 1

Input:

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

Output:

5

Note:

The subarray [1,2,1,2,3] (from index 0 to 4) contains elements 1 (frequency 2), 2 (frequency 2), and 3 (frequency 1). The set of distinct frequencies observed is {1, 2}, which has a size of 2. Since 2 <= k, this is a valid subarray. It is the longest such subarray.

2

Example 2

Input:

nums = [1,1,1,1,1], k = 1

Output:

5

Note:

The entire array [1,1,1,1,1] has only one element 1 with frequency 5. The set of distinct frequencies is {5}, which has a size of 1. Since 1 <= k, this is a valid subarray. It is the longest such subarray.

3

Example 3

Input:

nums = [1,2,3,4,5], k = 0

Output:

0

Note:

With k=0, no non-empty subarray can satisfy the condition. Any non-empty subarray will contain at least one element, which will have a frequency of at least 1, leading to at least one distinct frequency. Thus, the number of distinct frequencies will always be >= 1, violating freqCounts.size <= 0.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 0 <= k <= nums.length
  • The input array nums contains integers.
  • Time complexity: Aim for O(N) or O(N log N).
  • Space complexity: Aim for O(D) where D is the number of distinct elements in nums (at most O(N)).

What interviewers evaluate

  • Correctness: Does the solution accurately identify the longest balanced subarray for all valid inputs?
  • Efficiency: Is the chosen algorithm performant enough for large inputs (O(N) or O(N log N) time complexity)?
  • Data Structure Usage: Effective and appropriate use of hash maps (or similar structures) for frequency tracking.
  • Edge Case Handling: Correctly handles empty inputs, k=0, and scenarios where no valid subarray exists.
  • Code Quality: Readability, modularity, and clean implementation.

Loading editor...