Is Length of Longest Subarray With at Most K Frequency easy or hard?

The problem is classified as Medium difficulty. The challenge is recognizing that the constraint can be maintained with a sliding window and frequency map. Once the pattern is identified, the implementation is straightforward and linear time.

Length of Longest Subarray With at Most K Frequency Python/Java solution

Python solutions typically use a dictionary or collections.Counter for frequency tracking, while Java implementations use HashMap . Both implementations follow the same sliding window pattern with two pointers and run in O(n) time.

How to solve Length of Longest Subarray With at Most K Frequency in O(n)?

Use a sliding window and maintain a hash map that stores the frequency of elements in the current window. Expand the right pointer and update the frequency. If any element appears more than k times, move the left pointer and decrement counts until the window becomes valid. Track the maximum window length during the process.

What is the best approach for Length of Longest Subarray With at Most K Frequency?

The optimal approach uses a sliding window with a frequency hash map. Two pointers track the current window while a map stores how many times each value appears. When any frequency exceeds k, move the left pointer forward until the window becomes valid again. This solution runs in O(n) time with O(n) space.

Is Length of Longest Subarray With at Most K Frequency asked at Google/Amazon/Meta?

Problems involving sliding window frequency constraints frequently appear in interviews at companies like Amazon, Google, and Meta. Variants include longest substring with limited repeats or subarrays with frequency constraints. Interviewers use them to test window management and hash map usage.

What data structure is used in Length of Longest Subarray With at Most K Frequency?

The core data structure is a hash table (or dictionary) that stores the frequency of each element in the current window. Combined with two pointers for the sliding window, it allows constant‑time updates and checks while scanning the array.

What is the time complexity of Length of Longest Subarray With at Most K Frequency?

The optimal sliding window solution runs in O(n) time because each element enters and leaves the window at most once. Frequency updates and lookups in the hash map are O(1) on average. The auxiliary space is O(n) in the worst case if all elements are distinct.

Description Hints 2 Solution Video 21:52

2958. Length of Longest Subarray With at Most K Frequency

Medium60.4% acceptance4 companies

You are given an integer array nums and an integer k.

The frequency of an element x is the number of times it occurs in an array.

An array is called good if the frequency of each element in this array is less than or equal to k.

Return the length of the longest good subarray of nums.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,2,3,1,2,3,1,2], k = 2
Output: 6
Explanation: The longest possible good subarray is [1,2,3,1,2,3] since the values 1, 2, and 3 occur at most twice in this subarray. Note that the subarrays [2,3,1,2,3,1] and [3,1,2,3,1,2] are also good.
It can be shown that there are no good subarrays with length more than 6.

Example 2:

Input: nums = [1,2,1,2,1,2,1,2], k = 1
Output: 2
Explanation: The longest possible good subarray is [1,2] since the values 1 and 2 occur at most once in this subarray. Note that the subarray [2,1] is also good.
It can be shown that there are no good subarrays with length more than 2.

Example 3:

Input: nums = [5,5,5,5,5,5,5], k = 4
Output: 4
Explanation: The longest possible good subarray is [5,5,5,5] since the value 5 occurs 4 times in this subarray.
It can be shown that there are no good subarrays with length more than 4.

Constraints: