# 28.03.2024 [2958. Length of Longest Subarray With at Most K Frequency]
Max subarray length with frequencies <= `k` #medium
28.03.2024
2958. Length of Longest Subarray With at Most K Frequency medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/552
Problem TLDR
Max subarray length with frequencies <= k
#medium
Intuition
There is a known sliding window
pattern: the right pointer will increase the frequency and left pointer will decrease it. Not try to expand as much as possible, then shrink until conditions are met.
Approach
move the right pointer one position at a time
we can use
maxOf
in Kotlin ormax
in Rust
Complexity
Time complexity:
O(n)Space complexity:
O(n)
Code
fun maxSubarrayLength(nums: IntArray, k: Int): Int {
val freq = mutableMapOf<Int, Int>(); var j = 0
return nums.indices.maxOf { i ->
freq[nums[i]] = 1 + (freq[nums[i]] ?: 0)
while (freq[nums[i]]!! > k)
freq[nums[j]] = freq[nums[j++]]!! - 1
i - j + 1
}
}
pub fn max_subarray_length(nums: Vec<i32>, k: i32) -> i32 {
let (mut freq, mut j) = (HashMap::new(), 0);
(0..nums.len()).map(|i| {
*freq.entry(nums[i]).or_insert(0) += 1;
while freq[&nums[i]] > k {
*freq.get_mut(&nums[j]).unwrap() -= 1; j += 1
}
i - j + 1
}).max().unwrap() as i32
}