Count subarrays with k distinct integers

Array Hash Table Sliding Window Counting

19.0% acceptance

Mar 17, 2026

You are given an integer array nums and two integers k and m. Return an integer denoting the count of subarrays of nums such that: The subarray contains exactly k distinct integers. Within the subarray, each distinct integer appears at least m times.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_subarrays(nums: Vec<i32>, k: i32, m: i32) -> i64 {
    let n = nums.len();
    let k = k as usize;
    let m = m as usize;

    if k == 0 {
      return 0;
    }

    // Three-pointer O(n) approach.
    // For each right endpoint, valid left endpoints l satisfy:
    //   exactly k distinct values in [l..=right], each with freq >= m.
    //
    // Pointers:
    //   left_lo: smallest l where distinct(l,right) <= k   (at-most-k window)
    //   left_hi: smallest l where distinct(l,right) <= k-1 (at-most-(k-1) window)
    //   left_q:  largest  l where qualified(l,right) >= k  (at-least-k-qualified)
    //
    // Range with exactly k distinct: [left_lo, left_hi - 1]
    // Range with >= k qualified:     [0, left_q]
    // Valid: [left_lo, min(left_hi - 1, left_q)]

    use std::collections::HashMap;

    let mut freq_lo: HashMap<i32, usize> = HashMap::new();
    let mut distinct_lo = 0usize;
    let mut left_lo = 0usize;

    let mut freq_hi: HashMap<i32, usize> = HashMap::new();
    let mut distinct_hi = 0usize;
    let mut left_hi = 0usize;

    let mut freq_q: HashMap<i32, usize> = HashMap::new();
    let mut qualified_q = 0usize;
    let mut left_q = 0usize;

    let mut result = 0i64;

    for right in 0..n {
      let v = nums[right];

      // Pointer 1: at most k distinct
      {
        let e = freq_lo.entry(v).or_insert(0);
        if *e == 0 {
          distinct_lo += 1;
        }
        *e += 1;
      }
      while distinct_lo > k {
        let e = freq_lo.get_mut(&nums[left_lo]).unwrap();
        *e -= 1;
        if *e == 0 {
          distinct_lo -= 1;
        }
        left_lo += 1;
      }

      // Pointer 2: at most k-1 distinct
      {
        let e = freq_hi.entry(v).or_insert(0);
        if *e == 0 {
          distinct_hi += 1;
        }
        *e += 1;
      }
      while distinct_hi >= k {
        let e = freq_hi.get_mut(&nums[left_hi]).unwrap();
        *e -= 1;
        if *e == 0 {
          distinct_hi -= 1;
        }
        left_hi += 1;
      }

      // Pointer 3: advance left_q as far right as possible while qualified >= k
      {
        let e = freq_q.entry(v).or_insert(0);
        *e += 1;
        if *e == m {
          qualified_q += 1;
        }
      }
      while left_q <= right && qualified_q >= k {
        let val = nums[left_q];
        let f = *freq_q.get(&val).unwrap();
        if f == m && qualified_q == k {
          break;
        }
        if f == m {
          qualified_q -= 1;
        }
        *freq_q.get_mut(&val).unwrap() -= 1;
        left_q += 1;
      }

      // Count valid left endpoints
      if qualified_q >= k && left_hi > left_lo {
        let hi = std::cmp::min(left_hi - 1, left_q);
        if hi >= left_lo {
          result += (hi - left_lo + 1) as i64;
        }
      }
    }

    result
  }
}