Count complete subarrays in an array

Array Hash Table Sliding Window

75.9% acceptance

Feb 25, 2026

1128

You are given an array nums consisting of positive integers. We call a subarray of an array complete if the following condition is satisfied: The number of distinct elements in the subarray is equal to the number of distinct elements in the whole array. Return the number of complete subarrays. A subarray is a contiguous non-empty part of an array.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_complete_subarrays(nums: Vec<i32>) -> i32 {
    use std::collections::{HashMap, HashSet};
    let total_distinct = nums.iter().cloned().collect::<HashSet<_>>().len();
    let n = nums.len();
    let mut ans = 0i32;
    let mut freq: HashMap<i32, usize> = HashMap::new();
    let mut right = 0usize;
    for left in 0..n {
      while right < n && freq.len() < total_distinct {
        *freq.entry(nums[right]).or_insert(0) += 1;
        right += 1;
      }
      if freq.len() == total_distinct {
        ans += (n - right + 1) as i32;
      }
      // Remove left
      let e = freq.get_mut(&nums[left]).unwrap();
      *e -= 1;
      if *e == 0 { freq.remove(&nums[left]); }
    }
    ans
  }
}