Hard

Find X-Sum of All K-Long Subarrays II

LAB

For each length-k window, sum value*frequency for the x most frequent values, breaking ties by larger value.

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    1,
    2,
    2,
    3,
    4,
    2,
    3
  ],
  "k": 6,
  "x": 2
}

Output
[
  6,
  10,
  12
]

FUNCTION SHAPE

nums: intArrayk: intx: int→intArray

SOLUTION NOTE

Sliding window with two SortedLists tracking (frequency, value) pairs. Right list holds top x by frequency. Maintain sum of right for O(1) query.

Reveal reference solution +

pythonREFERENCE

from sortedcontainers import SortedList
from collections import Counter

def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:
    res = []
    left = SortedList()   # (freq, val) not in top x
    right = SortedList()  # (freq, val) in top x
    sum_right = 0
    freq = Counter()

    def add(val):
        nonlocal sum_right
        f = freq[val]
        if f > 0:
            if (f, val) in right:
                right.remove((f, val))
                sum_right -= f * val
            else:
                left.discard((f, val))
        freq[val] += 1
        f += 1
        left.add((f, val))
        # Move from left to right if needed
        while len(right) < x and left:
            item = left.pop(-1)
            right.add(item)
            sum_right += item[0] * item[1]
        # Swap if left has larger than right's smallest
        while left and right and left[-1] > right[0]:
            l_item = left.pop(-1)
            r_item = right.pop(0)
            left.add(r_item)
            right.add(l_item)
            sum_right += l_item[0] * l_item[1] - r_item[0] * r_item[1]

    def remove(val):
        nonlocal sum_right
        f = freq[val]
        if (f, val) in right:
            right.remove((f, val))
            sum_right -= f * val
        else:
            left.remove((f, val))
        freq[val] -= 1
        if freq[val] > 0:
            left.add((freq[val], val))
        # Rebalance
        while len(right) < x and left:
            item = left.pop(-1)
            right.add(item)
            sum_right += item[0] * item[1]

    for i, num in enumerate(nums):
        add(num)
        if i >= k - 1:
            res.append(sum_right)
            remove(nums[i - k + 1])
    return res

TimeO(n log k)

SpaceO(k)

Open on LeetCode ↗