Find X-Sum of All K-Long Subarrays II solution and explanation
Google
9 more videos on this problem
Find X-Sum of All K-Long Subarrays II | Detailed Intuition | Complete Dry Run | Leetcode 3321 | MIKcodestorywithMIK · 1:02:46 · 10K views
Find X-Sum of All K-Long Subarrays II - Leetcode 3321 - PythonNeetCodeIO · 29:25 · 6K views
Find X-Sum of All K-Long Subarrays II | LeetCode 3321 | Sliding Window & Two-Set OptimizationSanyam IIT Guwahati · 34:40 · 1K views
The interview ft. LeetCode | LC 3321. Find X-Sum of All K-Long Subarrays IICF Step · 29:12 · 1K views
3321. Find X-Sum of All K-Long Subarrays II (Leetcode Hard)Programming Live with Larry · 42:48 · 730 views
Daily Leetcode #2045: Nov 05, 2025 - 3321. Find X-Sum of All K-Long Subarrays IIProgramming Live with Larry · 48:29 · 599 views
3321. Find X-Sum of All K-Long Subarrays II | Leetcode Daily - PythonLeetcode Daily · 10:05 · 431 views
Find X Sum of All K Long Subarrays II | LeetCode 3321 - Pythonimpoldev · 23:28 · 337 views
Leetcode 3321. Find X-Sum of All K-Long Subarrays II | Sliding Window + SortedList | Python SolutionStatLearn Tech · 35:46 · 262 views
Leetcode 3321 🔥 Find X-Sum of All K-Long Subarrays II | DCC | Optimal Solution + Dry Run Study Placement · 34:18 · 189 views
The 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
xmost 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 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:
- For subarray
[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. - For subarray
[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. - For subarray
[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.length
Approach overview
Problem 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 1: Sliding Window with Priority Queue
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.
# Python code
from collections import Counter
from heapq import nlargest
def x_sum(nums, k, x):
n = len(nums)
result = []
for i in range(n - k + 1):
subarray = nums[i:i + k]
count = Counter(subarray)
# Using nlargest to get the top x elements by frequency and value
most_frequent = nlargest(x, count.items(), key=lambda item: (item[1], item[0]))
subarray_sum = sum(val * freq for val, freq in most_frequent)
result.append(subarray_sum)
return result
# Example Usage
nums = [1, 1, 2, 2, 3, 4, 2, 3]
k = 6
x = 2
print(x_sum(nums, k, x)) # Output: [6, 10, 12]// JavaScript code
function xSum(nums, k, x) {
function calculateXSum(subarray) {
const freq = {};
subarray.forEach(num => {
if (freq[num]) {
freq[num]++;
} else {
freq[num] = 1;
}
});
const sortedElements = Object.entries(freq)
.sort((a, b) => b[1] - a[1] || b[0] - a[0])
.slice(0, x);
return sortedElements.reduce((sum, [num, count]) => sum + num * count, 0);
}
const result = [];
for (let i = 0; i <= nums.length - k; i++) {
const subarray = nums.slice(i, i + k);
result.push(calculateXSum(subarray));
}
return result;
}
// Example Usage
const nums = [1, 1, 2, 2, 3, 4, 2, 3];
const k = 6;
const x = 2;
console.log(xSum(nums, k, x)); // Output: [6, 10, 12]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.
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.
Approach 2: Optimized Sliding Window with HashMap
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.
// Java code
import java.util.*;
public class XSum {
public static List<Integer> xSum(int[] nums, int k, int x) {
List<Integer> result = new ArrayList<>();
Map<Integer, Integer> count = new HashMap<>();
TreeMap<Integer, Set<Integer>> freqMap = new TreeMap<>(Collections.reverseOrder());
for (int i = 0; i < k; i++) {
int num = nums[i];
int prevCount = count.getOrDefault(num, 0);
count.put(num, prevCount + 1);
if (prevCount > 0) {
freqMap.get(prevCount).remove(num);
if (freqMap.get(prevCount).isEmpty()) {
freqMap.remove(prevCount);
}
}
freqMap.computeIfAbsent(prevCount + 1, key -> new HashSet<>()).add(num);
}
for (int i = k; i <= nums.length; i++) {
int sum = 0, taken = 0;
for (Map.Entry<Integer, Set<Integer>> entry : freqMap.entrySet()) {
for (int num : entry.getValue()) {
int takenNow = Math.min(x - taken, count.get(num));
sum += takenNow * num;
taken += takenNow;
if (taken == x) break;
}
if (taken == x) break;
}
result.add(sum);
if (i == nums.length) break;
int leftNum = nums[i - k];
int rightNum = nums[i];
int leftCount = count.getOrDefault(leftNum, 0);
count.put(leftNum, leftCount - 1);
if (leftCount <= 1) {
freqMap.get(leftCount).remove(leftNum);
if (freqMap.get(leftCount).isEmpty()) {
freqMap.remove(leftCount);
}
} else {
freqMap.get(leftCount).remove(leftNum);
freqMap.computeIfAbsent(leftCount - 1, key -> new HashSet<>()).add(leftNum);
}
int rightCount = count.getOrDefault(rightNum, 0);
count.put(rightNum, rightCount + 1);
freqMap.computeIfAbsent(rightCount + 1, key -> new HashSet<>()).add(rightNum);
if (rightCount > 0) {
freqMap.get(rightCount).remove(rightNum);
if (freqMap.get(rightCount).isEmpty()) {
freqMap.remove(rightCount);
}
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 1, 2, 2, 3, 4, 2, 3};
int k = 6, x = 2;
List<Integer> result = xSum(nums, k, x);
System.out.println(result);
}
}// C++ code
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <iostream>
using namespace std;
vector<int> xSum(vector<int>& nums, int k, int x) {
vector<int> result;
unordered_map<int, int> count;
map<int, set<int>, greater<int>> freqMap;
for (int i = 0; i < k; ++i) {
int num = nums[i];
int prevCount = count[num]++;
if (prevCount > 0) {
freqMap[prevCount].erase(num);
if (freqMap[prevCount].empty()) {
freqMap.erase(prevCount);
}
}
freqMap[prevCount + 1].insert(num);
}
for (int i = k; i <= nums.size(); ++i) {
int sum = 0, taken = 0;
for (auto& [freq, numsSet] : freqMap) {
for (int num : numsSet) {
int takenNow = min(x - taken, count[num]);
sum += takenNow * num;
taken += takenNow;
if (taken == x) break;
}
if (taken == x) break;
}
result.push_back(sum);
if (i == nums.size()) break;
int leftNum = nums[i - k];
int rightNum = nums[i];
int leftCount = count[leftNum]--;
if (leftCount > 1) {
freqMap[leftCount].erase(leftNum);
freqMap[leftCount - 1].insert(leftNum);
} else {
freqMap[leftCount].erase(leftNum);
if (freqMap[leftCount].empty()) freqMap.erase(leftCount);
}
int rightCount = count[rightNum]++;
if (rightCount > 0) {
freqMap[rightCount].erase(rightNum);
freqMap[rightCount + 1].insert(rightNum);
} else {
freqMap[1].insert(rightNum);
}
}
return result;
}
int main() {
vector<int> nums = {1, 1, 2, 2, 3, 4, 2, 3};
int k = 6, x = 2;
vector<int> result = xSum(nums, k, x);
for (int num : result) {
cout << num << " ";
}
return 0;
}Implemented using Java's TreeMap to maintain frequencies in descending order, this method efficiently manages subarray frequencies while sliding the window, making additions and deletions to the map as required. Java's data structures facilitate automatic ordering, which fits well with the requirements of this approach.
Time Complexity: O(n*logk) for TreeMap operations.
Space Complexity: O(k), for frequency management.
Complexity comparison
| 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) for TreeMap operations. |
Complexity analysis
| 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 |
Frequently asked questions
Is Find X-Sum of All K-Long Subarrays II easy or hard?
Find X-Sum of All K-Long Subarrays II is classified as Hard because it combines multiple concepts: sliding window optimization, dynamic frequency counting, and maintaining ranked elements efficiently. Implementing correct updates and rebalancing logic makes it challenging.
Find X-Sum of All K-Long Subarrays II Python/Java solution
Python implementations usually rely on heapq with a dictionary for frequency tracking, while Java solutions often use PriorityQueue, TreeMap, or ordered sets. Both follow the same sliding window idea and maintain the top x frequent elements dynamically.
How to solve Find X-Sum of All K-Long Subarrays II in O(n)?
A strict O(n) solution is generally not feasible because maintaining the top x frequent elements requires ordered updates when frequencies change. Most optimized implementations achieve O(n log k) using sliding window frequency tracking with heaps or balanced sets.
What is the best approach for Find X-Sum of All K-Long Subarrays II?
The most effective solution uses a sliding window with a frequency hash map and a structure that tracks the top x elements by (frequency, value). As the window moves, update counts for the entering and leaving elements and rebalance the top contributors. This keeps the X-sum updated in O(log k) time per step.
Is Find X-Sum of All K-Long Subarrays II asked at Google/Amazon/Meta?
Problems combining sliding windows with frequency ranking structures appear frequently in interviews at companies like Google, Amazon, and Meta. Variants often require maintaining top-k frequent elements or dynamic statistics while a window moves across the array.
What data structure is used in Find X-Sum of All K-Long Subarrays II?
The solution typically uses a hash map to maintain frequencies of elements in the current window and a heap or ordered set to rank elements by (frequency, value). These structures allow efficient updates and quick access to the top x contributors for the X-sum.
What is the time complexity of Find X-Sum of All K-Long Subarrays II?
The optimal solutions run in O(n log k) time, where n is the array length and k is the window size. Each window shift updates element frequencies and performs heap or balanced-set operations that cost O(log k). Space complexity is O(k) to store frequencies and ordering structures.