Sum of weighted modes in subarrays

Array Hash Table Sliding Window Counting Ordered Set

54.4% acceptance

Mar 31, 2026

You are given an integer array nums and an integer k. For every subarray of length k: The mode is defined as the element with the highest frequency. If there are multiple choices for a mode, the smallest such element is taken. The weight is defined as mode * frequency(mode). Return the sum of the weights of all subarrays of length k. Note: A subarray is a contiguous non-empty sequence of elements within an array. The frequency of an element x is the number of times it occurs in the array.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn mode_weight(nums: Vec<i32>, k: i32) -> i64 {
    use std::collections::BTreeSet;
    use std::collections::HashMap;
    use std::cmp::Reverse;

    let n = nums.len();
    let k = k as usize;
    let mut freq: HashMap<i32, i32> = HashMap::new();
    // BTreeSet of (Reverse(freq), val) so first() gives highest freq, smallest val
    let mut mode_set: BTreeSet<(Reverse<i32>, i32)> = BTreeSet::new();
    let mut result: i64 = 0;

    // Initialize first window
    for i in 0..k {
      let f = freq.entry(nums[i]).or_insert(0);
      if *f > 0 {
        mode_set.remove(&(Reverse(*f), nums[i]));
      }
      *f += 1;
      mode_set.insert((Reverse(*f), nums[i]));
    }

    // Get mode for first window
    let &(Reverse(mf), mv) = mode_set.iter().next().unwrap();
    result += mv as i64 * mf as i64;

    // Slide window
    for i in k..n {
      // Add nums[i]
      let f = freq.entry(nums[i]).or_insert(0);
      if *f > 0 {
        mode_set.remove(&(Reverse(*f), nums[i]));
      }
      *f += 1;
      mode_set.insert((Reverse(*f), nums[i]));

      // Remove nums[i - k]
      let old = nums[i - k];
      let f = freq.get_mut(&old).unwrap();
      mode_set.remove(&(Reverse(*f), old));
      *f -= 1;
      if *f > 0 {
        mode_set.insert((Reverse(*f), old));
      }

      let &(Reverse(mf), mv) = mode_set.iter().next().unwrap();
      result += mv as i64 * mf as i64;
    }

    result
  }
}