You are given an array nums of n integers and two integers k and x.
The x-sum of an array is calculated by the following procedure:
x most frequent elements. If two elements have the same number of occurrences, the element with the bigger value is considered more frequent.Note that if an array has less than x distinct elements, its x-sum is the sum of the array.
Return an integer array answer of length n - k + 1 where answer[i] is the x-sum of the subarray nums[i..i + k - 1].
Example 1:
Input: nums = [1,1,2,2,3,4,2,3], k = 6, x = 2
Output: [6,10,12]
Explanation:
[1, 1, 2, 2, 3, 4], only elements 1 and 2 will be kept in the resulting array. Hence, answer[0] = 1 + 1 + 2 + 2.[1, 2, 2, 3, 4, 2], only elements 2 and 4 will be kept in the resulting array. Hence, answer[1] = 2 + 2 + 2 + 4. Note that 4 is kept in the array since it is bigger than 3 and 1 which occur the same number of times.[2, 2, 3, 4, 2, 3], only elements 2 and 3 are kept in the resulting array. Hence, answer[2] = 2 + 2 + 2 + 3 + 3.Example 2:
Input: nums = [3,8,7,8,7,5], k = 2, x = 2
Output: [11,15,15,15,12]
Explanation:
Since k == x, answer[i] is equal to the sum of the subarray nums[i..i + k - 1].
Constraints:
nums.length == n1 <= n <= 1051 <= nums[i] <= 1091 <= x <= k <= nums.lengthProblem Overview: Given an integer array, you slide a window of size k across the array. For every window, compute the X-sum: consider the x most frequent numbers inside the window (ties resolved by larger value) and sum value * frequency for those selected numbers. Return the result for each window as it moves from left to right.
Approach 1: Sliding Window with Priority Queue (O(n log k) time, O(k) space)
The straightforward efficient solution combines a sliding window with a priority queue. Maintain a frequency map for elements inside the current window using a hash table. Each time the window moves, update the frequency of the incoming and outgoing elements. Push frequency updates into a max heap ordered by (frequency, value) so the most frequent and largest elements appear first. Extract the top x candidates to compute the X-sum. This approach is conceptually simple and works well when x is small relative to k, though repeated heap updates introduce a logarithmic cost.
Approach 2: Optimized Sliding Window with HashMap and Balanced Sets (O(n log k) time, O(k) space)
A more optimized implementation avoids repeatedly rebuilding heap state. Maintain a frequency map for the current window and split elements into two groups: the top x contributors and the remaining elements. The first group stores elements currently contributing to the X-sum, while the second group holds the rest. When the window shifts, update the frequency of the outgoing and incoming numbers, then rebalance the groups so the top group always contains the best x elements by (frequency, value). Track the running contribution value * frequency of elements inside the top group, adjusting it incrementally instead of recomputing from scratch. Balanced structures such as ordered sets, heaps, or maps keep insert/remove operations at O(log k).
Recommended for interviews: Start by explaining the sliding window with a frequency map since every subarray shares most elements with the previous one. Then introduce the priority queue or two-set optimization to efficiently track the top x contributors. Interviewers typically expect the optimized sliding window idea because it demonstrates understanding of dynamic frequency tracking and efficient rebalancing rather than recomputing results for every window.
We use a sliding window technique to generate subarrays of length k. For each subarray, we calculate the frequency of each element and use a priority queue to identify the top x frequent elements. The priority queue helps us efficiently keep track of the most frequent elements as we slide the window across the array.
We iterate through each possible starting index of the subarray using a loop. For each subarray, we count the occurrences of each number with a Counter. Using nlargest from the heapq module, we extract the top x elements sorted by frequency and then by value. These elements' contributions to the x-sum are calculated and added to the result list.
Python
JavaScript
Time Complexity: O((n-k+1)*k*logx), where logx is for maintaining the heap of the top x elements.
Space Complexity: O(k), for maintaining the counter.
This approach further optimizes by maintaining a frequency map which is updated as the window slides. Instead of recomputing the entire frequency map for each subarray, we adjust the map incrementally by adding a new element and removing the element that's no longer in the window. This reduces redundant calculations and improves efficiency.
This solution maintains a frequency map along with a map sorting the frequencies in descending order (to identify top x elements). As the window slides, the frequency map is incrementally updated to reflect the addition of the new number and the removal of the old number outside the window. This avoids full recomputation of frequencies.
Time Complexity: O(n*logk) due to logarithmic operations on the map.
Space Complexity: O(k), for storing frequency counts.
We use a hash table cnt to count the occurrences of each element in the window, an ordered set l to store the x elements with the highest occurrences in the window, and another ordered set r to store the remaining elements.
We maintain a variable s to represent the sum of the elements in l. Initially, we add the first k elements to the window, update the ordered sets l and r, and calculate the value of s. If the size of l is less than x and r is not empty, we repeatedly move the largest element from r to l until the size of l equals x, updating the value of s in the process. If the size of l is greater than x, we repeatedly move the smallest element from l to r until the size of l equals x, updating the value of s in the process. At this point, we can calculate the current window's x-sum and add it to the answer array. Then we remove the left boundary element of the window, update cnt, and update the ordered sets l and r, as well as the value of s. Continue traversing the array until the traversal is complete.
The time complexity is O(n times log k), and the space complexity is O(n). Here, n is the length of the array nums.
Similar problems:
| Approach | Complexity |
|---|---|
| Sliding Window with Priority Queue | Time Complexity: O((n-k+1)*k*logx), where logx is for maintaining the heap of the top x elements. |
| Optimized Sliding Window with HashMap | Time Complexity: O(n*logk) due to logarithmic operations on the map. |
| Hash Table + Ordered Set | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window + Priority Queue | O(n log k) | O(k) | Good general solution when implementing quickly using heaps |
| Optimized Sliding Window with HashMap and Rebalancing Sets | O(n log k) | O(k) | Best practical approach when maintaining a running X-sum efficiently |
Find X-Sum of All K-Long Subarrays II | Detailed Intuition | Complete Dry Run | Leetcode 3321 | MIK • codestorywithMIK • 9,702 views views
Watch 9 more video solutions →Practice Find X-Sum of All K-Long Subarrays II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor