Find X-Sum of All K-Long Subarrays I

main.md

Question

Approach

I slide a window of length k over nums. For each window I count frequencies of values (values are bounded <= 50), build pairs (freq, value) for values present in the window, sort those pairs by frequency descending and value descending (so ties favor the larger value), then keep only the top x pairs and sum freq * value for those pairs. If the window has fewer than x distinct values, the x-sum is simply the sum of the entire window.

Implementation

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

        for i in range(n - k + 1):
            cnt = [0] * (MAXV + 1)
            total_sum = 0
            distinct = 0
            for j in range(i, i + k):
                v = nums[j]
                if cnt[v] == 0:
                    distinct += 1
                cnt[v] += 1
                total_sum += v

            if distinct <= x:
                ans.append(total_sum)
            else:
                pairs = []
                for val in range(1, MAXV + 1):
                    f = cnt[val]
                    if f > 0:
                        pairs.append((f, val))
                pairs.sort(key=lambda p: (-p[0], -p[1]))
                s = 0
                for idx in range(min(x, len(pairs))):
                    f, val = pairs[idx]
                    s += f * val
                ans.append(s)

        return ans

Complexities

• Time: O(n)
• Space: O(V)