Frontend School

Longest Subarray with Bounded Frequency Difference

DSA
hard

Longest Subarray with Bounded Frequency Difference

Hard
Arrays
Hashing
Sliding Window
TreeMap
Priority Queue

Overview

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.

What you need to do / Task

Implement a function longestSubarrayBoundedFreq(nums: number[], k: number): number that returns the length of the longest contiguous subarray satisfying the condition.

Input & output

  • 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.
  • Returns: An integer, the maximum length of a contiguous subarray meeting the criteria.

Clarifications

  • A subarray with only one distinct element always satisfies the condition (difference is 0, which is <= k for any k >= 0). Thus, the minimum possible return value is 1 if nums is not empty.
  • If all elements in a subarray are distinct, all their frequencies are 1, so minFreq=1, maxFreq=1, and the difference is 0. This is always valid for k >= 0.

Examples

1

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:
    • Remove 1 (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:
    • Remove 2 (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:
    • Remove 1 (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.
2

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.

3

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

Constraints & assumptions

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

What interviewers evaluate

  • Correctly identifying and implementing the sliding window pattern.
  • Efficiently tracking individual element frequencies within the window.
  • Efficiently querying and updating the minimum and maximum frequencies among all elements currently in the window.
  • Handling edge cases such as k=0 or arrays with all identical elements.
  • Code clarity, organization, and correct use of data structures for optimal performance.

Loading editor...