Find X-Sum of All K-Long Subarrays I - Problem

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:

Count the occurrences of all elements in the array.
Keep only the occurrences of the top x most frequent elements. If two elements have the same number of occurrences, the element with the bigger value is considered more frequent.
Calculate the sum of the resulting array.

Note: 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].

Input & Output

Example 1 — Basic Case

$ Input: nums = [3,2,3,1], k = 3, x = 2

› Output: [8,5]

💡 Note: For subarray [3,2,3]: frequencies are {3:2, 2:1}. Since x=2, take all elements: 3×2 + 2×1 = 8. For subarray [2,3,1]: frequencies are {2:1, 3:1, 1:1}. Take top 2 by frequency,value: 3×1 + 2×1 = 5.

Example 2 — Less Than X Elements

$ Input: nums = [1,1,2], k = 2, x = 4

› Output: [2,3]

💡 Note: For subarray [1,1]: only 1 distinct element < x=4, so sum all: 1+1 = 2. For subarray [1,2]: only 2 distinct elements < x=4, so sum all: 1+2 = 3.

Example 3 — Tiebreaker by Value

$ Input: nums = [2,4,2,4], k = 4, x = 2

› Output: [12]

💡 Note: Subarray [2,4,2,4] has frequencies {2:2, 4:2}. Both have same frequency, so tiebreaker by value: take 4 (bigger) and 2. Sum: 4×2 + 2×2 = 12.

Constraints

1 ≤ n ≤ 50
1 ≤ nums[i] ≤ 50
1 ≤ k ≤ n
1 ≤ x ≤ k

Visualization

Tap to expand

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The problem requires calculating x-sum for all k-length subarrays, where x-sum is the sum of top x most frequent elements (with value as tiebreaker). The Sort-First Optimization approach is most efficient, leveraging the constraint that nums[i] ≤ 50 to use array-based frequency counting instead of hash maps, achieving O((n-k+1) × min(k,50)) time complexity compared to the brute force O((n-k+1) × k × log k). The key insight is using sliding window to maintain frequency state efficiently while avoiding expensive sorting operations through bounded value iteration.

Common Approaches

✓ Brute Force - Process Each Subarray

⏱️ Time: O((n-k+1) * k * log k) Space: O(k)

For each possible k-length subarray, count element frequencies, sort by frequency (with value as tiebreaker), take top x elements, and sum their contributions. If fewer than x distinct elements exist, sum all elements.

Sliding Window with Frequency Map

⏱️ Time: O((n-k+1) * k * log k) Space: O(k)

Use sliding window technique to maintain a frequency map as we move through subarrays. When sliding, remove the leftmost element and add the new rightmost element, then recalculate x-sum only for the updated frequencies.

Sort-First Optimization

⏱️ Time: O((n-k+1) * min(k, 50)) Space: O(1)

Instead of sorting for each window, pre-process the array to identify frequency patterns and optimize x-sum calculation. This approach leverages the constraint that element values are small (≤50) to use more efficient data structures.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

Time & Space Complexity

Time Complexity

⏱️

✓ Linear Growth

Space Complexity

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

342 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen