# 29.03.2024 [2962. Count Subarrays Where Max Element Appears at Least K Times]
Count subarrays with at least `k` array max in #medium
29.03.2024
2962. Count Subarrays Where Max Element Appears at Least K Times medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/553
Problem TLDR
Count subarrays with at least k
array max in #medium
Intuition
Let’s observe an example 1 3 3
:
// inverse the problem
// [1], [3], [3], [1 3], [1 3 3], [3 3] // 6
// 1 3 3 ck c
// j .
// i . 1
// i 1 3
// i 2
// j
// j 1 4
// 6-4=2
The problem is more simple if we invert it: count subarrays with less than k
maximums. Then it is just a two-pointer problem: increase by one, then shrink until condition < k
met.
Another way, is to solve problem at face: left border is the count we need - all subarrays before our j..i
will have k
max elements if j..i
have them.
Approach
Let’s implement both.
Complexity
Time complexity:
O(n)Space complexity:
O(1)
Code
fun countSubarrays(nums: IntArray, k: Int): Long {
val n = nums.size.toLong()
val m = nums.max(); var ck = 0; var j = 0
return n * (n + 1) / 2 + nums.indices.sumOf { i ->
if (nums[i] == m) ck++
while (ck >= k) if (nums[j++] == m) ck--
-(i - j + 1).toLong()
}
}
pub fn count_subarrays(nums: Vec<i32>, k: i32) -> i64 {
let (mut j, mut curr, m) = (0, 0, *nums.iter().max().unwrap());
(0..nums.len()).map(|i| {
if nums[i] == m { curr += 1 }
while curr >= k { if nums[j] == m { curr -= 1 }; j += 1 }
j as i64
}).sum()
}