MediumNo. 2958
Length of Longest Subarray With at Most K Frequency — LeetCode 2958 Python Solution
- Pattern
- Sliding Window
- Topics
- Array, Hash Table, Sliding Window
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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.
Example
- 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.
Python solution
class Solution:
def maxSubarrayLength(self, nums: List[int], k: int) -> int:
cnt = defaultdict(int)
ans = j = 0
for i, x in enumerate(nums):
cnt[x] += 1
while cnt[x] > k:
cnt[nums[j]] -= 1
j += 1
ans = max(ans, i - j + 1)
return ansComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2958. Length of Longest Subarray With at Most K Frequency is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.
The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0219 | Contains Duplicate II | Easy |
| 0480 | Sliding Window Median | Hard |
| 0594 | Longest Harmonious Subsequence | Easy |
| 0632 | Smallest Range Covering Elements from K Lists | Hard |
| 0904 | Fruit Into Baskets | Medium |
| 0930 | Binary Subarrays With Sum | Medium |
Frequently asked questions
- How hard is LeetCode 2958. Length of Longest Subarray With at Most K Frequency?
LeetCode 2958. Length of Longest Subarray With at Most K Frequency is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2958. Length of Longest Subarray With at Most K Frequency?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2958. Length of Longest Subarray With at Most K Frequency?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2958. Length of Longest Subarray With at Most K Frequency cover?
LeetCode 2958. Length of Longest Subarray With at Most K Frequency is tagged Array, Hash Table and Sliding Window on LeetCode.