Longest Subarray with Bounded Frequency Difference
In network analytics, identifying stable traffic patterns is crucial. Sometimes, we want to find segments of data where the relative prevalence of different events remains within a certain tolerance. This problem asks you to find the longest contiguous subarray where the difference between the most frequent and least frequent element counts is bounded by a given value k.
Implement a function longestSubarrayBoundedFreq(nums: number[], k: number): number that returns the length of the longest contiguous subarray satisfying the condition.
nums: An array of integers representing data points.k: A non-negative integer representing the maximum allowed difference between the highest and lowest frequencies within any valid subarray.<= k for any k >= 0). Thus, the minimum possible return value is 1 if nums is not empty.minFreq=1, maxFreq=1, and the difference is 0. This is always valid for k >= 0.Examples
Example 1
Input:
nums = [1, 2, 1, 3, 4, 1], k = 0
Output:
4
Note:
Let's trace the sliding window:
[1] -> Freq: {1:1}. minF=1, maxF=1. diff=0. OK. maxLen=1.[1,2] -> Freq: {1:1, 2:1}. minF=1, maxF=1. diff=0. OK. maxLen=2.[1,2,1] -> Freq: {1:2, 2:1}. minF=1, maxF=2. diff=1. > k=0. Invalid. Shrink L:
nums[0]): Freq: {1:1, 2:1}. Window [2,1]. minF=1, maxF=1. diff=0. OK. maxLen remains 2.[2,1,3] -> Add 3 (nums[3]): Freq: {1:1, 2:1, 3:1}. minF=1, maxF=1. diff=0. OK. maxLen=3.[2,1,3,4] -> Add 4 (nums[4]): Freq: {1:1, 2:1, 3:1, 4:1}. minF=1, maxF=1. diff=0. OK. maxLen=4.[2,1,3,4,1] -> Add 1 (nums[5]): Freq: {1:2, 2:1, 3:1, 4:1}. minF=1, maxF=2. diff=1. > k=0. Invalid. Shrink L:
nums[1]): Freq: {1:2, 3:1, 4:1}. Window [1,3,4,1]. minF=1, maxF=2. diff=1. > k=0. Invalid. Shrink L:nums[2]): Freq: {1:1, 3:1, 4:1}. Window [3,4,1]. minF=1, maxF=1. diff=0. OK. maxLen remains 4.
The longest valid subarray is [2,1,3,4] with length 4.Example 2
Input:
nums = [5, 5, 5, 5], k = 0
Output:
4
Note:
The entire array [5, 5, 5, 5] has frequencies {5:4}. The difference between min and max frequency is 4 - 4 = 0, which is <= k. Thus, the longest subarray is the entire array itself.
Example 3
Input:
nums = [10, 20, 10, 20, 30], k = 1
Output:
5
Note:
The entire array [10, 20, 10, 20, 30] has frequencies {10:2, 20:2, 30:1}. The minimum frequency is 1 (for '30'), and the maximum frequency is 2 (for '10' and '20'). Their difference is 2 - 1 = 1, which is <= k. Thus, the longest subarray is the entire array itself.
Constraints
1 <= nums.length <= 10^50 <= nums[i] <= 10^90 <= k <= 10^5k=0 or arrays with all identical elements.Loading editor...