Find X-Sum of All K-Long Subarrays I

Difficulty: Easy | Acceptance: 76.10% | Paid: No Topics: Array, Hash Table, Sliding Window, Heap (Priority Queue)

Problem Description

You are given an array of integers nums, and two integers k and x.

The x-sum of a subarray is calculated as follows:

1. Count the frequency of each element in the subarray.
2. Take the x most frequent elements. If there are ties in frequency, prefer larger elements.
3. Sum these x elements, each multiplied by its frequency.

Return an array containing the x-sum of every subarray of length k.

Table of Contents

• Examples
• Constraints
• Brute Force
• Sliding Window with Hash Map
• Sliding Window with Counter

Examples

Example 1

Input: nums = [1,1,2,2,3,4,2,3], k = 6, x = 2
Output: [6,10,12]
Explanation: 
- Subarray [1,1,2,2,3,4]: Frequencies are {1:2, 2:2, 3:1, 4:1}. Top 2 by (freq, value) are 2 and 1. X-sum = 2*2 + 1*2 = 6.
- Subarray [1,2,2,3,4,2]: Frequencies are {1:1, 2:3, 3:1, 4:1}. Top 2 by (freq, value) are 2 and 4. X-sum = 2*3 + 4*1 = 10.
- Subarray [2,2,3,4,2,3]: Frequencies are {2:3, 3:2, 4:1}. Top 2 by (freq, value) are 2 and 3. X-sum = 2*3 + 3*2 = 12.

Example 2

Input: nums = [3,8,7,8,7,5], k = 2, x = 2
Output: [11,15,15,15,12]
Explanation:
- Subarray [3,8]: Frequencies are {3:1, 8:1}. Top 2 are 8 and 3. X-sum = 8*1 + 3*1 = 11.
- Subarray [8,7]: Frequencies are {8:1, 7:1}. Top 2 are 8 and 7. X-sum = 8*1 + 7*1 = 15.
- Subarray [7,8]: Frequencies are {7:1, 8:1}. Top 2 are 8 and 7. X-sum = 8*1 + 7*1 = 15.
- Subarray [8,7]: Frequencies are {8:1, 7:1}. Top 2 are 8 and 7. X-sum = 8*1 + 7*1 = 15.
- Subarray [7,5]: Frequencies are {7:1, 5:1}. Top 2 are 7 and 5. X-sum = 7*1 + 5*1 = 12.

Constraints

1 <= nums.length <= 50
1 <= nums[i] <= 50
1 <= k <= nums.length
1 <= x <= number of distinct elements in the subarray

Brute Force

Intuition For each subarray of length k, count frequencies using a hash map, sort elements by (frequency, value) in descending order, and sum the top x elements.

Steps

• Iterate through all starting positions of subarrays of length k
• For each subarray, build a frequency map
• Convert the map to a list of (value, frequency) pairs
• Sort by (frequency, value) in descending order
• Sum the top x elements multiplied by their frequencies

from typing import List
from collections import defaultdict

class Solution:
    def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:
        n = len(nums)
        result = []
        
        for i in range(n - k + 1):
            freq = defaultdict(int)
            for j in range(i, i + k):
                freq[nums[j]] += 1
            
            items = list(freq.items())
            items.sort(key=lambda p: (p[1], p[0]), reverse=True)
            
            x_sum = 0
            for j in range(min(x, len(items))):
                x_sum += items[j][0] * items[j][1]
            
            result.append(x_sum)
        
        return result

Complexity

• Time: O(n × k × log(k)) where n is the length of nums
• Space: O(k) for the frequency map
• Notes: Simple but not optimal for large inputs

Sliding Window with Hash Map

Intuition Use a sliding window to maintain frequencies efficiently. As we move the window, we update the frequency map by removing the leftmost element and adding the new rightmost element.

Steps

• Initialize the frequency map for the first window
• Calculate the x-sum for the first window
• Slide the window one position at a time:
  • Decrement frequency of the element leaving the window
  • Remove it from the map if frequency becomes 0
  • Increment frequency of the new element entering the window
  • Calculate the x-sum for the current window

from typing import List
from collections import defaultdict

class Solution:
    def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:
        n = len(nums)
        result = []
        freq = defaultdict(int)
        
        for i in range(k):
            freq[nums[i]] += 1
        
        def calculate_x_sum():
            items = list(freq.items())
            items.sort(key=lambda p: (p[1], p[0]), reverse=True)
            x_sum = 0
            for j in range(min(x, len(items))):
                x_sum += items[j][0] * items[j][1]
            return x_sum
        
        result.append(calculate_x_sum())
        
        for i in range(k, n):
            left = nums[i - k]
            freq[left] -= 1
            if freq[left] == 0:
                del freq[left]
            
            freq[nums[i]] += 1
            result.append(calculate_x_sum())
        
        return result

Complexity

• Time: O(n × k × log(k)) where n is the length of nums
• Space: O(k) for the frequency map
• Notes: More efficient than brute force for window updates, but still requires sorting for each window

Sliding Window with Counter

Intuition Use Python’s Counter for efficient frequency counting and heapq’s nlargest to find the top x elements without full sorting.

Steps

• Use a Counter to maintain frequencies for the sliding window
• For each window position, use heapq.nlargest to get the top x elements
• Calculate the x-sum from these top elements

from typing import List
from collections import Counter
import heapq

class Solution:
    def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:
        n = len(nums)
        result = []
        counter = Counter(nums[:k])
        
        def calculate_x_sum():
            top_x = heapq.nlargest(x, counter.items(), key=lambda p: (p[1], p[0]))
            return sum(val * freq for val, freq in top_x)
        
        result.append(calculate_x_sum())
        
        for i in range(k, n):
            left = nums[i - k]
            counter[left] -= 1
            if counter[left] == 0:
                del counter[left]
            
            counter[nums[i]] += 1
            result.append(calculate_x_sum())
        
        return result

Complexity

• Time: O(n × k × log(k)) where n is the length of nums
• Space: O(k) for the frequency map
• Notes: Using Counter/heap can be more efficient in practice for finding top x elements