Find x sum of all k long subarrays i

Array Hash Table Sliding Window Heap (Priority Queue)

76.1% acceptance

Feb 23, 2026

558

320

You are given an array nums of n integers and two integers k and x. The x-sum of an array is calculated by the following procedure: Count the occurrences of all elements in the array. Keep only the occurrences of the top x most frequent elements. If two elements have the same number of occurrences, the element with the bigger value is considered more frequent. Calculate the sum of the resulting array. Note that if an array has less than x distinct elements, its x-sum is the sum of the array. Return an integer array answer of length n - k + 1 where answer[i] is the x-sum of the subarray nums[i..i + k - 1].

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_x_sum(nums: Vec<i32>, k: i32, x: i32) -> Vec<i32> {
    let k = k as usize;
    let x = x as usize;
    let n = nums.len();
    let mut result = Vec::new();
    
    for i in 0..=(n - k) {
      let window = &nums[i..i + k];
      let mut freq = std::collections::HashMap::new();
      for &v in window {
        *freq.entry(v).or_insert(0i32) += 1;
      }
      let mut entries: Vec<(i32, i32)> = freq.into_iter().collect();
      // Sort by (frequency desc, value desc)
      entries.sort_unstable_by(|a, b| {
        b.1.cmp(&a.1).then(b.0.cmp(&a.0))
      });
      let sum: i32 = entries.iter().take(x).map(|(val, cnt)| val * cnt).sum();
      result.push(sum);
    }
    result
  }
}