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

  • 1 <= n == nums.length <= 50
  • 1 <= nums[i] <= 50
  • 1 <= x <= k <= nums.length

Solution

Method 1 – Sliding Window + Frequency Map + Heap

Intuition

For each k-length subarray, we want the sum of the x most frequent elements (with ties broken by larger value). We can use a frequency map and a heap to efficiently get the x most frequent elements as the window slides.

Approach

  1. Use a sliding window of size k over nums.
  2. For each window:
    • Count the frequency of each element in the 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).
  3. Slide the window and repeat.
  4. 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
33
34
35
36

class Solution {
public:
    vector<int> xSumOfSubarrays(vector<int>& nums, int k, int x) {
        int n = nums.size();
        vector<int> ans;
        unordered_map<int, int> freq;
        for (int i = 0; i < k; ++i) freq[nums[i]]++;
        auto get_xsum = [&]() {
            vector<pair<int, int>> v(freq.begin(), freq.end());
            sort(v.begin(), v.end(), [](auto& a, auto& b) {
                if (a.second != b.second) return a.second > b.second;
                return a.first > b.first;
            });
            int sum = 0, cnt = 0;
            for (auto& [num, f] : v) {
                if (cnt == x) break;
                int take = min(f, x - cnt);
                sum += num * take;
                cnt += take;
            }
            if (v.size() < x) {
                sum = 0;
                for (auto& [num, f] : v) sum += num * f;
            }
            return sum;
        };
        ans.push_back(get_xsum());
        for (int i = k; i < n; ++i) {
            freq[nums[i-k]]--;
            if (freq[nums[i-k]] == 0) freq.erase(nums[i-k]);
            freq[nums[i]]++;
            ans.push_back(get_xsum());
        }
        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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

func xSumOfSubarrays(nums []int, k, x int) []int {
    n := len(nums)
    ans := []int{}
    freq := map[int]int{}
    for i := 0; i < k; i++ {
        freq[nums[i]]++
    }
    getXSum := func() int {
        type pair struct{ num, cnt int }
        v := []pair{}
        for num, cnt := range freq {
            v = append(v, pair{num, cnt})
        }
        sort.Slice(v, func(i, j int) bool {
            if v[i].cnt != v[j].cnt { return v[i].cnt > v[j].cnt }
            return v[i].num > v[j].num
        })
        sum, cnt := 0, 0
        for _, p := range v {
            if cnt == x { break }
            take := p.cnt
            if cnt+take > x { take = x - cnt }
            sum += p.num * take
            cnt += take
        }
        if len(v) < x {
            sum = 0
            for _, p := range v { sum += p.num * p.cnt }
        }
        return sum
    }
    ans = append(ans, getXSum())
    for i := k; i < n; i++ {
        freq[nums[i-k]]--
        if freq[nums[i-k]] == 0 { delete(freq, nums[i-k]) }
        freq[nums[i]]++
        ans = append(ans, getXSum())
    }
    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
26
27
28
29
30
31

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
26
27
28
29
30

class Solution {
    fun xSumOfSubarrays(nums: IntArray, k: Int, x: Int): IntArray {
        val n = nums.size
        val ans = IntArray(n - k + 1)
        val freq = mutableMapOf<Int, Int>()
        for (i in 0 until k) freq[nums[i]] = freq.getOrDefault(nums[i], 0) + 1
        fun getXSum(): Int {
            val v = freq.entries.map { it.toPair() }.toMutableList()
            v.sortWith(compareByDescending<Pair<Int, Int>> { it.second }.thenByDescending { it.first })
            var sum = 0
            var cnt = 0
            for ((num, f) in v) {
                if (cnt == x) break
                val take = minOf(f, x - cnt)
                sum += num * take
                cnt += take
            }
            if (v.size < x) sum = v.sumOf { it.first * it.second }
            return sum
        }
        ans[0] = getXSum()
        for (i in k until n) {
            freq[nums[i - k]] = freq[nums[i - k]]!! - 1
            if (freq[nums[i - k]] == 0) freq.remove(nums[i - k])
            freq[nums[i]] = freq.getOrDefault(nums[i], 0) + 1
            ans[i - k + 1] = getXSum()
        }
        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
 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
33
34
35
36
37

impl Solution {
    pub fn x_sum_of_subarrays(nums: Vec<i32>, k: i32, x: i32) -> Vec<i32> {
        use std::collections::HashMap;
        let n = nums.len();
        let mut ans = Vec::new();
        let mut freq = HashMap::new();
        for i in 0..k as usize {
            *freq.entry(nums[i]).or_insert(0) += 1;
        }
        let get_xsum = |freq: &HashMap<i32, i32>| -> i32 {
            let mut v: Vec<_> = freq.iter().collect();
            v.sort_by(|a, b| b.1.cmp(a.1).then(b.0.cmp(a.0)));
            if v.len() < x as usize {
                return v.iter().map(|(&num, &cnt)| num * cnt).sum();
            }
            let mut cnt = 0;
            let mut sum = 0;
            for (&num, &f) in v.iter() {
                if cnt == x { break; }
                let take = std::cmp::min(f, x - cnt);
                sum += num * take;
                cnt += take;
            }
            sum
        };
        ans.push(get_xsum(&freq));
        for i in k as usize..n {
            *freq.get_mut(&nums[i - k as usize]).unwrap() -= 1;
            if freq[&nums[i - k as usize]] == 0 {
                freq.remove(&nums[i - k as usize]);
            }
            *freq.entry(nums[i]).or_insert(0) += 1;
            ans.push(get_xsum(&freq));
        }
        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
26
27
28
29

class Solution {
    xSumOfSubarrays(nums: number[], k: number, x: number): number[] {
        const n = nums.length;
        const ans: number[] = [];
        const freq = new Map<number, number>();
        for (let i = 0; i < k; i++) freq.set(nums[i], (freq.get(nums[i]) ?? 0) + 1);
        function getXSum(): number {
            const v = Array.from(freq.entries());
            v.sort((a, b) => b[1] !== a[1] ? b[1] - a[1] : b[0] - a[0]);
            if (v.length < x) return v.reduce((s, [num, cnt]) => s + num * cnt, 0);
            let cnt = 0, sum = 0;
            for (const [num, f] of v) {
                if (cnt === x) break;
                const take = Math.min(f, x - cnt);
                sum += num * take;
                cnt += take;
            }
            return sum;
        }
        ans.push(getXSum());
        for (let i = k; i < n; i++) {
            freq.set(nums[i - k], freq.get(nums[i - k])! - 1);
            if (freq.get(nums[i - k]) === 0) freq.delete(nums[i - k]);
            freq.set(nums[i], (freq.get(nums[i]) ?? 0) + 1);
            ans.push(getXSum());
        }
        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.