Find X-Sum of All K-Long Subarrays I
EasyUpdated: Nov 5, 2025
Practice on:
Problem
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
xmost 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].
Examples
Example 1
Input: nums = [1,1,2,2,3,4,2,3], k = 6, x = 2
Output: [6,10,12]
Explanation:
* For subarray `[1, 1, 2, 2, 3, 4]`, only elements 1 and 2 will be kept in the resulting array. Hence, `answer[0] = 1 + 1 + 2 + 2`.
* For subarray `[1, 2, 2, 3, 4, 2]`, only elements 2 and 4 will be kept in the resulting array. Hence, `answer[1] = 2 + 2 + 2 + 4`. Note that 4 is kept in the array since it is bigger than 3 and 1 which occur the same number of times.
* For subarray `[2, 2, 3, 4, 2, 3]`, only elements 2 and 3 are kept in the resulting array. Hence, `answer[2] = 2 + 2 + 2 + 3 + 3`.
Example 2
Input: nums = [3,8,7,8,7,5], k = 2, x = 2
Output: [11,15,15,15,12]
Explanation:
Since `k == x`, `answer[i]` is equal to the sum of the subarray `nums[i..i + k
- 1]`.
Constraints
1 <= n == nums.length <= 501 <= nums[i] <= 501 <= x <= k <= nums.length
Solution
Method 1 – Sliding Window with Frequency Map and Max Heap
Intuition
For each subarray of length k, we want to compute the sum of the x most frequent elements, breaking ties by choosing the larger value. We use a frequency map to count occurrences and a max heap to efficiently retrieve the top x elements. As the window slides, we update the frequency map and recalculate the x-sum for each window.
Approach
- Initialize a frequency map for the first window of size
k. - For each window:
- Update the frequency map by removing the outgoing element and adding the incoming element.
- Use a max heap (priority queue) to get the top
xelements by frequency, breaking ties by value. - Calculate the x-sum for the current window and store it in the result.
- Return the result array after processing all windows.
Complexity
- ⏰ Time complexity:
O(n * k log k)– For each window, we sort or heapify up tokelements. - 🧺 Space complexity:
O(n + k)– For the frequency map and heap.
Code
C++
using namespace std;
class Solution {
public:
vector<int> findXSum(vector<int>& nums, int k, int x) {
int n = nums.size();
vector<int> answer;
unordered_map<int, int> freq;
for (int j = 0; j < k; j++) freq[nums[j]]++;
answer.push_back(calculateXSum(freq, x));
for (int i = 1; i <= n - k; i++) {
freq[nums[i - 1]]--;
if (freq[nums[i - 1]] == 0) freq.erase(nums[i - 1]);
freq[nums[i + k - 1]]++;
answer.push_back(calculateXSum(freq, x));
}
return answer;
}
private:
int calculateXSum(const unordered_map<int, int>& freq, int x) {
priority_queue<pair<int, int>> pq;
for (const auto& entry : freq) pq.push({entry.second, entry.first});
int sum = 0, cnt = 0;
while (!pq.empty() && cnt < x) {
auto [f, num] = pq.top(); pq.pop();
sum += num * f;
cnt++;
}
return sum;
}
};
Go
func findXSum(nums []int, k, x int) []int {
n := len(nums)
ans := []int{}
freq := map[int]int{}
for j := 0; j < k; j++ {
freq[nums[j]]++
}
ans = append(ans, calculateXSum(freq, x))
for i := 1; i <= n-k; i++ {
freq[nums[i-1]]--
if freq[nums[i-1]] == 0 {
delete(freq, nums[i-1])
}
freq[nums[i+k-1]]++
ans = append(ans, calculateXSum(freq, x))
}
return ans
}
func calculateXSum(freq map[int]int, x int) int {
type pair struct{ freq, num int }
pq := []pair{}
for num, f := range freq {
pq = append(pq, pair{f, num})
}
sort.Slice(pq, func(i, j int) bool {
if pq[i].freq != pq[j].freq { return pq[i].freq > pq[j].freq }
return pq[i].num > pq[j].num
})
sum := 0
cnt := 0
for _, p := range pq {
if cnt == x { break }
sum += p.num * p.freq
cnt++
}
return sum
}
Java
class Solution {
public int[] findXSum(int[] nums, int k, int x) {
int n = nums.length;
int[] answer = new int[n - k + 1];
Map<Integer, Integer> freq = new HashMap<>();
for (int j = 0; j < k; j++) freq.put(nums[j], freq.getOrDefault(nums[j], 0) + 1);
answer[0] = calculateXSum(freq, x);
for (int i = 1; i <= n - k; i++) {
freq.put(nums[i - 1], freq.get(nums[i - 1]) - 1);
if (freq.get(nums[i - 1]) == 0) freq.remove(nums[i - 1]);
freq.put(nums[i + k - 1], freq.getOrDefault(nums[i + k - 1], 0) + 1);
answer[i] = calculateXSum(freq, x);
}
return answer;
}
private int calculateXSum(Map<Integer, Integer> freq, int x) {
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] != a[0] ? b[0] - a[0] : b[1] - a[1]);
for (var entry : freq.entrySet()) pq.offer(new int[]{entry.getValue(), entry.getKey()});
int sum = 0, cnt = 0;
while (!pq.isEmpty() && cnt < x) {
int[] top = pq.poll();
sum += top[1] * top[0];
cnt++;
}
return sum;
}
}
Kotlin
class Solution {
fun findXSum(nums: IntArray, k: Int, x: Int): IntArray {
val n = nums.size
val answer = IntArray(n - k + 1)
val freq = mutableMapOf<Int, Int>()
for (j in 0 until k) freq[nums[j]] = freq.getOrDefault(nums[j], 0) + 1
answer[0] = calculateXSum(freq, x)
for (i in 1..n - k) {
freq[nums[i - 1]] = freq[nums[i - 1]]!! - 1
if (freq[nums[i - 1]] == 0) freq.remove(nums[i - 1])
freq[nums[i + k - 1]] = freq.getOrDefault(nums[i + k - 1], 0) + 1
answer[i] = calculateXSum(freq, x)
}
return answer
}
private fun calculateXSum(freq: Map<Int, Int>, x: Int): Int {
val pq = PriorityQueue<Pair<Int, Int>>(compareByDescending<Pair<Int, Int>> { it.first }.thenByDescending { it.second })
for ((num, f) in freq) pq.offer(Pair(f, num))
var sum = 0
var cnt = 0
while (pq.isNotEmpty() && cnt < x) {
val (f, num) = pq.poll()
sum += num * f
cnt++
}
return sum
}
}
Python
from collections import Counter
import heapq
class Solution:
def findXSum(self, nums: list[int], k: int, x: int) -> list[int]:
n = len(nums)
answer = []
freq = Counter(nums[:k])
answer.append(self.calculate_xsum(freq, x))
for i in range(1, n - k + 1):
freq[nums[i - 1]] -= 1
if freq[nums[i - 1]] == 0:
del freq[nums[i - 1]]
freq[nums[i + k - 1]] += 1
answer.append(self.calculate_xsum(freq, x))
return answer
def calculate_xsum(self, freq: Counter, x: int) -> int:
heap = [(-f, -num) for num, f in freq.items()]
heapq.heapify(heap)
sum_ = 0
cnt = 0
while heap and cnt < x:
f, num = heapq.heappop(heap)
sum_ += -num * -f
cnt += 1
return sum_
Rust
use std::collections::{HashMap, BinaryHeap};
impl Solution {
pub fn find_x_sum(nums: Vec<i32>, k: i32, x: i32) -> Vec<i32> {
let n = nums.len();
let mut answer = Vec::new();
let mut freq = HashMap::new();
for j in 0..k as usize {
*freq.entry(nums[j]).or_insert(0) += 1;
}
answer.push(Self::calculate_xsum(&freq, x));
for i in 1..=n - k as usize {
*freq.get_mut(&nums[i - 1]).unwrap() -= 1;
if freq[&nums[i - 1]] == 0 {
freq.remove(&nums[i - 1]);
}
*freq.entry(nums[i + k as usize - 1]).or_insert(0) += 1;
answer.push(Self::calculate_xsum(&freq, x));
}
answer
}
fn calculate_xsum(freq: &HashMap<i32, i32>, x: i32) -> i32 {
let mut heap = BinaryHeap::new();
for (&num, &f) in freq {
heap.push((f, num));
}
let mut sum = 0;
let mut cnt = 0;
while let Some((f, num)) = heap.pop() {
if cnt == x { break; }
sum += num * f;
cnt += 1;
}
sum
}
}
TypeScript
class Solution {
findXSum(nums: number[], k: number, x: number): number[] {
const n = nums.length;
const answer: number[] = [];
const freq = new Map<number, number>();
for (let j = 0; j < k; j++) freq.set(nums[j], (freq.get(nums[j]) ?? 0) + 1);
answer.push(this.calculateXSum(freq, x));
for (let i = 1; i <= n - k; i++) {
freq.set(nums[i - 1], freq.get(nums[i - 1])! - 1);
if (freq.get(nums[i - 1]) === 0) freq.delete(nums[i - 1]);
freq.set(nums[i + k - 1], (freq.get(nums[i + k - 1]) ?? 0) + 1);
answer.push(this.calculateXSum(freq, x));
}
return answer;
}
private calculateXSum(freq: Map<number, number>, x: number): number {
const arr = Array.from(freq.entries());
arr.sort((a, b) => b[1] !== a[1] ? b[1] - a[1] : b[0] - a[0]);
let sum = 0, cnt = 0;
for (const [num, f] of arr) {
if (cnt === x) break;
sum += num * f;
cnt++;
}
return sum;
}
}