Distinct numbers in each subarray

Array Hash Table Sliding Window

77.3% acceptance

Mar 31, 2026

157

You are given an integer array nums of length n and an integer k. Your task is to find the number of distinct elements in every subarray of size k within nums. Return an array ans such that ans[i] is the count of distinct elements in nums[i..(i + k - 1)] for each index 0 <= i < n - k.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn distinct_numbers(nums: Vec<i32>, k: i32) -> Vec<i32> {
    let k = k as usize;
    let n = nums.len();
    let mut freq: HashMap<i32, i32> = HashMap::new();
    let mut result = Vec::with_capacity(n - k + 1);
    for i in 0..k {
      *freq.entry(nums[i]).or_insert(0) += 1;
    }
    result.push(freq.len() as i32);
    for i in k..n {
      *freq.entry(nums[i]).or_insert(0) += 1;
      let count = freq.get_mut(&nums[i - k]).unwrap();
      *count -= 1;
      if *count == 0 {
        freq.remove(&nums[i - k]);
      }
      result.push(freq.len() as i32);
    }
    result
  }
}