Skip to main content
Talentd

Find X-Sum of All K-Long Subarrays II - Solution & Explanation

HardArrayHash TableSliding WindowHeap (Priority Queue)14 min readAsked at: Google, Bloomberg
Practice this problem

Problem Statement

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 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 == n
  • 1 <= n <= 105
  • 1 <= nums[i] <= 109
  • 1 <= 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.

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(n*logk) due to logarithmic operations on the map.
Space Complexity: O(k), for storing frequency counts.

Try this approach in the editor →

Approach 3: Hash Table + Ordered Set

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:

Code

PythonJavaC++

Python

Java

C++

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(k), for maintaining the counter.

Optimized Sliding Window with HashMap

Time Complexity: O(n*logk) due to logarithmic operations on the map.
Space Complexity: O(k), for storing frequency counts.

Hash Table + Ordered Set—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sliding Window + Priority QueueO(n log k)O(k)Good general solution when implementing quickly using heaps
Optimized Sliding Window with HashMap and Rebalancing SetsO(n log k)O(k)Best practical approach when maintaining a running X-sum efficiently

Video Solution

Find X-Sum of All K-Long Subarrays II | Detailed Intuition | Complete Dry Run | Leetcode 3321 | MIK • codestorywithMIK • 10,077 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Find X-Sum of All K-Long Subarrays II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays