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 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].

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

1
2
3
4
5
6
7
8
9


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

  • nums.length == n
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= x <= k <= nums.length

Solution

Method 1 – Sliding Window + Frequency Map + Heap (Optimized for Large n)

Intuition

For each k-length subarray, we want the sum of the x most frequent elements (with ties broken by larger value). Since n can be large, we need an efficient way to maintain frequencies as the window slides.

Approach

  1. Use a sliding window of size k over nums.
  2. Maintain a frequency map for the current window.
  3. For each window:
    • Use a heap (max-heap by frequency, then value) to get the x most frequent elements.
    • If there are fewer than x distinct elements, sum the whole window.
    • Otherwise, sum the elements corresponding to the x most frequent elements (each counted as many times as they appear in the window).
  4. Slide the window and update the frequency map efficiently.
  5. Return the answer array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import java.util.*;
class Solution {
    public int[] xSumOfSubarrays(int[] nums, int k, int x) {
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        Map<Integer, Integer> freq = new HashMap<>();
        for (int i = 0; i < k; i++) freq.put(nums[i], freq.getOrDefault(nums[i], 0) + 1);
        for (int i = 0; i <= n - k; i++) {
            List<int[]> v = new ArrayList<>();
            for (var e : freq.entrySet()) v.add(new int[]{e.getKey(), e.getValue()});
            v.sort((a, b) -> b[1] != a[1] ? b[1] - a[1] : b[0] - a[0]);
            int sum = 0, cnt = 0;
            for (var p : v) {
                if (cnt == x) break;
                int take = Math.min(p[1], x - cnt);
                sum += p[0] * take;
                cnt += take;
            }
            if (v.size() < x) {
                sum = 0;
                for (var p : v) sum += p[0] * p[1];
            }
            ans[i] = sum;
            if (i + k < n) {
                freq.put(nums[i], freq.get(nums[i]) - 1);
                if (freq.get(nums[i]) == 0) freq.remove(nums[i]);
                freq.put(nums[i + k], freq.getOrDefault(nums[i + k], 0) + 1);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def xSumOfSubarrays(self, nums: list[int], k: int, x: int) -> list[int]:
        from collections import Counter
        n = len(nums)
        ans = []
        freq = Counter(nums[:k])
        def get_xsum():
            v = sorted(freq.items(), key=lambda p: (-p[1], -p[0]))
            if len(v) < x:
                return sum(num * cnt for num, cnt in v)
            cnt, s = 0, 0
            for num, f in v:
                if cnt == x: break
                take = min(f, x - cnt)
                s += num * take
                cnt += take
            return s
        ans.append(get_xsum())
        for i in range(k, n):
            freq[nums[i-k]] -= 1
            if freq[nums[i-k]] == 0:
                del freq[nums[i-k]]
            freq[nums[i]] += 1
            ans.append(get_xsum())
        return ans

Complexity

  • ⏰ Time complexity: O(n * k log k), since for each window we sort up to k elements.
  • 🧺 Space complexity: O(k), for the frequency map and heap.