Compute the X-sum of every subarray of length K, where the X-sum is formed by the sum of the most frequent values in that window.
Problem
Given an integer array nums and two integers k and x, consider every contiguous subarray of length k.
For each such subarray, define its X-sum as follows:
- Count the frequency of each distinct value inside the subarray.
- Choose the
xdistinct values with the highest frequency. - If multiple values have the same frequency, prefer the larger value.
- The X-sum is the sum of all occurrences of those chosen values within the subarray.
Return an array containing the X-sum for every subarray of length k, in order from left to right.
Notes
- If a window contains fewer than
xdistinct values, use all of them. - Each window is evaluated independently.
- Ties are broken by value, not by position.
Input Format
nums: integer arrayk: window lengthx: number of distinct values to include in the X-sum
You must compute the answer for every contiguous subarray of length k.
Output Format
Return an array of length nums.length - k + 1, where the i-th element is the X-sum of the subarray nums[i..i+k-1].
Constraints
1 <= nums.length1 <= k <= nums.length1 <= x- Values in
numsmay be negative or positive integers - The answer for each window depends only on the multiset of values in that window
Example 1
Input
nums = [1,2,2,3,3,3], k = 4, x = 2
Output
[9, 13, 12]
Explanation
Windows of length 4:
- [1,2,2,3] -> frequencies: 2:2, 3:1, 1:1. Pick 2 and 3 => 2+2+3 = 7.
- [2,2,3,3] -> frequencies: 2:2, 3:2. Pick both => 2+2+3+3 = 10.
- [2,3,3,3] -> frequencies: 3:3, 2:1. Pick 3 and 2 => 3+3+3+2 = 11.
Note: This is an illustrative example of the window-ranking rule.
Example 2
Input
nums = [5,5,1,1,2], k = 3, x = 1
Output
[10, 2, 2]
Explanation
Windows:
- [5,5,1] -> value 5 has highest frequency, so X-sum = 5+5 = 10.
- [5,1,1] -> value 1 has highest frequency, so X-sum = 1+1 = 2.
- [1,1,2] -> value 1 has highest frequency, so X-sum = 1+1 = 2.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.