Count the number of good subarrays

Array Hash Table Sliding Window

65.9% acceptance

Feb 25, 2026

1558

Given an integer array nums and an integer k, return the number of good subarrays of nums. A subarray arr is good if there are at least k pairs of indices (i, j) such that i < j and arr[i] == arr[j]. A subarray is a contiguous non-empty sequence of elements within an array.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_good(nums: Vec<i32>, k: i32) -> i64 {
    use std::collections::HashMap;
    let k = k as i64;
    let n = nums.len();
    let mut freq: HashMap<i32, i64> = HashMap::new();
    let mut pairs: i64 = 0;
    let mut ans: i64 = 0;
    let mut left = 0usize;

    for right in 0..n {
      let e = freq.entry(nums[right]).or_insert(0);
      pairs += *e;
      *e += 1;

      // Shrink from left until pairs < k (smallest invalid window)
      while pairs >= k {
        let lv = nums[left];
        let lf = freq.get_mut(&lv).unwrap();
        *lf -= 1;
        pairs -= *lf; // pairs removed = new freq (after decrement)
        left += 1;
      }
      // [left, right] has < k pairs.
      // All [l, right] with l in [0, left-1] have >= k pairs.
      ans += left as i64;
    }
    ans
  }
}