Count subarrays where max element appears at least k times

Array Sliding Window

62.4% acceptance

Feb 25, 2026

1709

You are given an integer array nums and a positive integer k. Return the number of subarrays where the maximum element of nums appears at least k times in that subarray.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_subarrays(nums: Vec<i32>, k: i32) -> i64 {
    let max_val = *nums.iter().max().unwrap();
    let k = k as usize;
    let mut positions: Vec<usize> = Vec::new();
    let mut ans = 0i64;
    for (i, &v) in nums.iter().enumerate() {
      if v == max_val {
        positions.push(i);
      }
      let cnt = positions.len();
      if cnt >= k {
        // leftmost valid start: any index 0..=positions[cnt-k]
        ans += (positions[cnt - k] + 1) as i64;
      }
    }
    ans
  }
}