LeetCode Entry

2958. Length of Longest Subarray With at Most K Frequency

28.03.2024 medium 2024 kotlin rust

Max subarray length with frequencies <= k

2958. Length of Longest Subarray With at Most K Frequency medium blog post substack youtube

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: 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 or max 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
    }