Find X-Sum of All K-Long Subarrays I — Easy Problem & Solution

Problem statement

The x-sum of an array is computed like this:

1. Count how often each value occurs.
2. Keep only the occurrences of the x most frequent values. When two values are equally frequent, the larger value counts as more frequent.
3. The x-sum is the sum of the kept occurrences (each kept value times its count).

If the array has fewer than x distinct values, the x-sum is simply the sum of the array.

Given an array nums of length n and integers k and x, return an array answer of length n - k + 1 where answer[i] is the x-sum of the subarray nums[i..i + k - 1].

Example 1

Input: nums = [4,4,1,2,2,3,1], k = 5, x = 2
Output: [12,8,6]
Explanation: Window `[4,4,1,2,2]`: 4 and 2 both appear twice, so 4·2 + 2·2 = 12. Window `[4,1,2,2,3]`: 2 appears twice, then 4 wins the tie among the singles: 4 + 4 = 8. Window `[1,2,2,3,1]`: 2·2 + 1·2 = 6.

Example 2

Input: nums = [5,6,5,6], k = 2, x = 2
Output: [11,11,11]
Explanation: Each window has two distinct values, so its x-sum is its plain sum.

Example 3

Input: nums = [7,3,7], k = 3, x = 1
Output: [14]

Constraints

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

How to solve Find X-Sum of All K-Long Subarrays I

Directly simulate the definition for every window: count, rank by frequency with the larger value winning ties, and sum the top x groups.

Approach

1. For each start i from 0 to n - k, count the values in nums[i..i+k-1].
2. Collect the distinct values and sort them by count descending, then by value descending.
3. Add value × count for the first min(x, distinct) of them; that is answer[i].

Why it works

The ordering (count, then value, both descending) is a strict total order on the distinct values, so "the x most frequent values" is well defined and the sort produces exactly them. Summing whole groups matches the rule that all occurrences of a kept value count.

Complexity

• Time — O((n - k + 1) · k log k)
• Space — O(k)

Pitfalls

• Ties go to the larger value, not the one seen first.
• Add every occurrence of a kept value (value × count), not just the value once.
• For the larger variant (n up to 10^5) the window must be maintained incrementally with two ordered sets; here brute force suffices.

Reference solution

Python

from typing import List

def findXSum(nums: List[int], k: int, x: int) -> List[int]:
    res = []
    for i in range(len(nums) - k + 1):
        cnt = {}
        for v in nums[i:i + k]:
            cnt[v] = cnt.get(v, 0) + 1
        ranked = sorted(cnt.items(), key=lambda p: (-p[1], -p[0]))
        res.append(sum(v * c for v, c in ranked[:x]))
    return res

JavaScript

var findXSum = function(nums, k, x) {
    var res = [];
    for (var i = 0; i + k <= nums.length; i++) {
        var freq = new Array(51).fill(0);
        for (var j = i; j < i + k; j++) freq[nums[j]]++;
        // key = count * 64 + value orders by count, then value (value < 64)
        var keys = [];
        for (var v = 1; v <= 50; v++) if (freq[v] > 0) keys.push(freq[v] * 64 + v);
        keys.sort(function(a, b) { return b - a; });
        var sum = 0;
        for (var t = 0; t < x && t < keys.length; t++) sum += (keys[t] % 64) * Math.floor(keys[t] / 64);
        res.push(sum);
    }
    return res;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Available Captures for Rook Easy
• Delete Columns to Make Sorted Easy
• Maximize Sum Of Array After K Negations Easy
• Nearest Smaller Element Easy
• Minimum Positive Sum Subarray Easy
• Valid Boomerang Easy