Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

An x-sum keeps all occurrences of the highest-ranked distinct values. Values are ranked by frequency first, then by larger numeric value on a frequency tie. The small constraints allow rebuilding this ranking independently for each window.

Approach

For each contiguous window of length k, count its values in a frequency map and turn the entries into a list. Python sorts by increasing value and then stably by increasing frequency, placing the highest-ranked entries at the end; it pops up to x entries from that end. JavaScript sorts directly by decreasing frequency and decreasing value, then takes the first x entries.

Sum value * frequency for each selected entry and append the total to the answer. If fewer than x distinct values exist, both versions select all of them. Multiplying by the frequency includes every occurrence of a chosen value, rather than counting each selected distinct value only once.

class Solution:
    def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:
        n = len(nums)
        res = []

        for i in range(k - 1, n):
            map = defaultdict(int)
            for j in range(i - (k - 1), i + 1):
                map[nums[j]] += 1

            curr = 0
            arr = list(map.items())
            arr.sort()
            arr.sort(key = lambda x: x[1])

            for j in range(x):
                if not arr:
                    break
                key, val = arr.pop()
                curr += key * val
            res.append(curr)

        return res

Complexity analysis

Let n = nums.length and w = n - k + 1. Time is O(wklog(k + 1)) in the worst case, including O(w) work when k = 1. Auxiliary space is O(k) for each window's frequency map, sorted entries and JavaScript's selected-entry slice, excluding the O(w) output.