Watch 10 video solutions for Find X-Sum of All K-Long Subarrays II, a hard level problem involving Array, Hash Table, Sliding Window. This walkthrough by codestorywithMIK has 9,702 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |