Find X-Sum of All K-Long Subarrays I
Problem
The x-sum of an array: count every element's occurrences, keep only the x most frequent elements (if two elements occur the same number of times, the one with the bigger value wins), then sum the kept occurrences. If an array has fewer than x distinct values, its x-sum is just the sum of the whole array.
Given nums, k and x, return an array answer of length n − k + 1 where answer[i] is the x-sum of the window nums[i..i + k − 1].
nums = [1,1,2,2,3,4,2,3], k = 6, x = 2[6, 10, 12]def findXSum(nums, k, x):
n = len(nums)
ans = []
for i in range(n - k + 1):
window = nums[i:i + k]
cnt = {} # value -> occurrences
for v in window:
cnt[v] = cnt.get(v, 0) + 1
# sort by (count, value) descending; bigger value breaks ties
items = sorted(cnt.items(), key=lambda p: (p[1], p[0]), reverse=True)
s = 0
for v, c in items[:x]: # keep the top x distinct values
s += v * c # add all their occurrences
ans.append(s)
return ansfunction findXSum(nums, k, x) {
const n = nums.length, ans = [];
for (let i = 0; i <= n - k; i++) {
const window = nums.slice(i, i + k);
const cnt = new Map(); // value -> occurrences
for (const v of window) cnt.set(v, (cnt.get(v) || 0) + 1);
// sort by count desc, then value desc to break ties
const items = [...cnt.entries()].sort(
(a, b) => b[1] - a[1] || b[0] - a[0]);
let s = 0;
for (const [v, c] of items.slice(0, x)) s += v * c;
ans.push(s);
}
return ans;
}int[] findXSum(int[] nums, int k, int x) {
int n = nums.length;
int[] ans = new int[n - k + 1];
for (int i = 0; i <= n - k; i++) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int j = i; j < i + k; j++)
cnt.merge(nums[j], 1, Integer::sum);
// sort by count desc, then value desc to break ties
List<int[]> items = new ArrayList<>();
for (var e : cnt.entrySet())
items.add(new int[]{e.getKey(), e.getValue()});
items.sort((a, b) -> b[1] != a[1] ? b[1] - a[1] : b[0] - a[0]);
int s = 0;
for (int t = 0; t < x && t < items.size(); t++)
s += items.get(t)[0] * items.get(t)[1];
ans[i] = s;
}
return ans;
}vector<int> findXSum(vector<int>& nums, int k, int x) {
int n = nums.size();
vector<int> ans;
for (int i = 0; i <= n - k; i++) {
map<int, int> cnt; // value -> occurrences
for (int j = i; j < i + k; j++) cnt[nums[j]]++;
vector<pair<int,int>> items(cnt.begin(), cnt.end());
// sort by count desc, then value desc to break ties
sort(items.begin(), items.end(), [](auto& a, auto& b){
return a.second != b.second ? a.second > b.second
: a.first > b.first; });
int s = 0;
for (int t = 0; t < x && t < (int)items.size(); t++)
s += items[t].first * items[t].second;
ans.push_back(s);
}
return ans;
}Explanation
The constraints here are tiny (n ≤ 50), so we can afford the brute-force-per-window approach: independently solve the x-sum for each length-k subarray.
For a single window we first build a frequency map cnt that maps each value to how many times it appears. This is the heart of the problem — the x-sum cares about occurrences, not positions.
Next we decide which values to keep. We sort the distinct values by (count, value) in descending order. Sorting by count first picks the most frequent elements; using the value as the secondary key implements the tie-break rule that "if two elements have the same number of occurrences, the bigger value is more frequent."
We then keep the first x entries and add value × count for each — that is the sum of all their occurrences. If the window has fewer than x distinct values, items[:x] simply returns them all, so the x-sum becomes the sum of the whole window, exactly as the note requires.
Repeating this for every starting index i from 0 to n − k yields the answer array of length n − k + 1. The window slides one step at a time, which is why this lives under sliding window — though with these limits we rebuild the count from scratch each time for clarity.