Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Neighboring windows differ in only one incoming and one outgoing occurrence. Maintain the ranking of distinct values instead of rebuilding it. Split (frequency, value) pairs into the best x entries and the remaining entries, while maintaining the selected entries' weighted sum.

Approach

Use ordered collections top and low, with every pair in top ranked above every pair in low. When a value's frequency changes, remove its old pair from the appropriate collection, subtracting its contribution if it was selected. Update the frequency and insert a new pair into low only if the frequency remains positive.

Fill vacant positions in top using the largest pairs from low. Then swap the best unselected pair with the worst selected pair while their ordering is wrong, adjusting the running sum each time. Pair ordering enforces both frequency priority and the larger-value tie-break.

Add each incoming occurrence and remove the occurrence leaving the window. Once a full window exists, append the maintained sum. When fewer than x values are present, all are selected.

class Solution:
    def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:
        n = len(nums)
        res = []
        fm = defaultdict(int)
        top = SortedList()
        low = SortedList()
        curr = 0

        def change(num, count):
            nonlocal curr

            # remove previous state if present
            prev = (fm[num], num)
            if fm[num]:
                if prev in low: low.discard(prev)
                else:
                    top.discard(prev)
                    curr -= fm[num] * num

            fm[num] += count

            # add to low
            if fm[num]: low.add((fm[num], num))

            # rebalance if top is not full or we have elemnts to swap with low
            while low and len(top) < x:
                freq, key = low.pop(-1)
                curr += freq * key
                top.add((freq, key))

            while low and low[-1] > top[0]:
                freq, key = low.pop(-1)
                xfreq, xkey = top.pop(0)
                curr = curr - xfreq * xkey + freq * key
                low.add((xfreq, xkey))
                top.add((freq, key))

        for i in range(n):
            change(nums[i], 1) # add current element
            if i >= k: change(nums[i - k], -1) # remove leftmost element
            if i >= k - 1: res.append(curr)

        return res

Complexity analysis

Let n = nums.length, U be the number of distinct values in the entire input, and D the maximum number of distinct values concurrently represented in the ordered collections. Because insertion precedes removal, D <= min(U, k + 1). Each frequency change alters only one ranked pair, requiring O(1) promotions or swaps. JavaScript's AVL operations give O(n log(D + 1)) time with expected hash-map access. Python uses block-based SortedList containers: approximately logarithmic updates give a practical O(n log(D + 1)) estimate, but a conservative worst-case update bound is O(D), hence O(n*D) total. Both retain zero-count frequency keys, so auxiliary space is O(U + D), not just current-window distinct values, excluding the O(n-k+1) returned sums.