Problem Statement in English

You’re given a 0-indexed integer array nums and two integers k and x. A subarray is called k-long if its length is equal to k.

Return an array such that for every k-long subarray of nums, it contains the x sum of that subarray. The x sum of a subarray is defined as the sum of the x largest unique elements in that subarray. If there are fewer than x unique elements in the subarray, the x sum is defined as the sum of all the unique elements.

If there are 2 elements with the same frequency, the element with the larger value is considered larger.

Approach

We can use a sliding window approach to find all k-long subarrays and their x sums efficiently. The idea is to maintain a hashmap to count the frequency of elements in the current window and a sorted list to calculate their x sum.

  1. Initialize a hashmap to keep track of the frequency of elements in the current window.
  2. Use a sliding window to iterate through the array and maintain the current window of size k.
  3. For each window, calculate the x sum by taking the x largest unique elements from the sorted list of elements in the window.
  4. Append the x sum to the result list.

Solution in Python


class Solution:
    def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:
        hm = defaultdict(int)

        l = 0
        res = []

        for r in range(len(nums)):
            hm[nums[r]] += 1
            t = r - l + 1

            if t < k:
                continue

            while t > k:
                hm[nums[l]] -= 1
                l += 1
                t -= 1

            arr = sorted(((v,k) for k, v in hm.items()), reverse=True)
            s = 0
            for i in range(min(len(hm), x)):
                s += arr[i][0] * arr[i][1]
            res.append(s)

        return res

Complexity

  • Time: $O(n \times k \times \log(k))$
    Since for each of the n elements we might have to sort up to k elements in the hashmap.

  • Space: $O(k)$
    Since we are using a hashmap to store at most k elements.

And we are done.