# Find X-Sum of All K-Long Subarrays II **Difficulty:** HARD [External](https://leetcode.com/problems/find-x-sum-of-all-k-long-subarrays-ii) Canonical: https://scaleengineer.com/dsa/problems/find-x-sum-of-all-k-long-subarrays-ii **Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window) **Data structures:** Array, Hash Table, Heap (Priority Queue) --- ## 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** 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` # Approaches ## Brute Force Iteration The most straightforward method is to iterate through each of the `n - k + 1` possible subarrays of length `k`. For each subarray, we perform the full x-sum calculation from scratch. This involves counting element frequencies, sorting them according to the problem's criteria, identifying the top `x` elements, and summing their occurrences. **Time:** O((n - k) * k log k) - For each of the `n - k + 1` windows, we build a frequency map in O(k) time. Then, we sort the distinct elements. If there are `D` distinct elements (where `D <= k`), sorting takes O(D log D). In the worst case, `D=k`, so sorting is O(k log k). The total time is dominated by this, resulting in O((n - k + 1) * k log k). · **Space:** O(k) - For each window, we create a frequency map and a list that can store up to `k` distinct elements in the worst case. This space is reused for each window. **Pros:** Simple to understand and implement.; Correct for all cases, assuming no time constraints. **Cons:** Highly inefficient due to redundant computations for overlapping parts of subarrays.; Will likely result in a 'Time Limit Exceeded' error for large inputs as specified in the constraints. ### Explanation We use a loop that iterates from `i = 0` to `n - k`. In each iteration, `i` represents the starting index of a new subarray. Inside the loop, for the subarray `nums[i...i+k-1]`: 1. A `HashMap` is used to store the frequency of each number in the current `k`-length subarray. We iterate from `j = i` to `i+k-1` to populate this map. 2. The entries of the frequency map are then transferred to a list. 3. This list is sorted. The sorting criteria are: primarily by frequency in descending order, and secondarily by the element's value in descending order (for tie-breaking). 4. We determine the number of top elements to consider, which is `min(x, number of distinct elements)`. 5. We iterate through these top elements, and for each one, we add `value * frequency` to a running sum for the current subarray. 6. This sum is the x-sum for the subarray starting at `i`, and it's added to our final answer array. This process is repeated for all `n - k + 1` subarrays. ```java import java.util.*; class Solution { public long[] getXSum(int[] nums, int k, int x) { int n = nums.length; long[] answer = new long[n - k + 1]; for (int i = 0; i <= n - k; i++) { Map freqMap = new HashMap<>(); for (int j = i; j < i + k; j++) { freqMap.put(nums[j], freqMap.getOrDefault(nums[j], 0) + 1); } List> entries = new ArrayList<>(freqMap.entrySet()); entries.sort((a, b) -> { if (!a.getValue().equals(b.getValue())) { return b.getValue().compareTo(a.getValue()); } return b.getKey().compareTo(a.getKey()); }); long currentXSum = 0; for (int j = 0; j < Math.min(x, entries.size()); j++) { Map.Entry entry = entries.get(j); currentXSum += (long) entry.getKey() * entry.getValue(); } answer[i] = currentXSum; } return answer; } } ``` ### Algorithm * Initialize an empty list `answer` to store the results. * Iterate with a loop from `i = 0` to `n - k` to represent the starting index of each subarray. * For each subarray `nums[i...i+k-1]`: 1. Create a `HashMap` to count the frequency of each element within this specific subarray. 2. Convert the `HashMap` entries into a `List`. 3. Sort this list based on the specified criteria: primarily by frequency in descending order, and secondarily by element value in descending order for tie-breaking. 4. Initialize a variable `currentXSum` to zero. 5. Iterate through the top `min(x, list.size())` elements of the sorted list. 6. For each of these top elements, add its total contribution (`value * frequency`) to `currentXSum`. 7. Add `currentXSum` to the `answer` list. * After the loop finishes, return the `answer` array. ## Sliding Window with Two Balanced Trees This optimized approach uses a sliding window to avoid recomputing the x-sum from scratch for each subarray. We maintain the state of the window using a frequency map and two ordered sets (e.g., `TreeSet`s). One set, `topX`, stores the current top `x` most frequent elements, while the other, `others`, stores the rest. As the window slides one position to the right, we efficiently update the frequencies and the sets by removing the outgoing element and adding the incoming one. The sets are rebalanced, and the x-sum is updated incrementally. **Time:** O((n - k) log k) - Initializing the first window takes O(k log k). Each of the `n - k` sliding steps involves a few updates on the `TreeSet`s. Each `TreeSet` operation (add, remove, poll) takes O(log D) time, where `D` is the number of distinct elements in the window (`D <= k`). Thus, each slide takes O(log k) time on average. · **Space:** O(k) - The `freqMap` and the two `TreeSet`s can store up to `k` distinct elements in total. **Pros:** Highly efficient and passes for large inputs.; Avoids redundant calculations by updating the window state incrementally. **Cons:** More complex to implement correctly compared to the brute-force approach.; Requires careful management of data structures and edge cases, especially with the comparator and sum updates. ### Explanation We use a `HashMap` to store the frequencies of elements within the current window. Two `TreeSet`s, `topX` and `others`, are used to partition the distinct elements. They store pairs of `(value, frequency)`. A custom comparator ensures they are ordered by frequency (descending) and then value (descending). * `topX` will hold at most `x` elements that are currently the most frequent. * `others` will hold the rest. * We also maintain a running sum, `xSum`, which is the sum of `value * frequency` for all elements in `topX`. **Initialization**: The first window (`nums[0...k-1]`) is processed to populate the `freqMap`, `topX`, `others`, and the initial `xSum`. **Sliding**: For each subsequent window, we slide by one element: 1. **Remove Element**: The element leaving the window (`outVal`) is processed. Its frequency is decremented. It's removed from whichever set (`topX` or `others`) it belongs to. If it was in `topX`, `xSum` is updated. Its new `(value, frequency)` pair (if frequency > 0) is added to `others` for re-evaluation. 2. **Add Element**: The element entering the window (`inVal`) is processed. Its frequency is incremented. Its old `(value, frequency)` pair is removed from its set. The new pair is added to `others`. 3. **Rebalance**: After the updates, the sets might not satisfy the invariant. We rebalance them by moving elements between `topX` and `others` until `topX` contains the `x` elements with the highest scores. `xSum` is updated whenever an element moves into or out of `topX`. This update-and-rebalance cycle is much faster than a full recalculation. ```java import java.util.*; class Solution { public long[] getXSum(int[] nums, int k, int x) { int n = nums.length; long[] answer = new long[n - k + 1]; Comparator comp = (a, b) -> { if (a[1] != b[1]) { return Long.compare(b[1], a[1]); } return Long.compare(b[0], a[0]); }; TreeSet topX = new TreeSet<>(comp); TreeSet others = new TreeSet<>(comp); Map freqMap = new HashMap<>(); long xSum = 0; for (int i = 0; i < k; i++) { freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0) + 1); } for (Map.Entry entry : freqMap.entrySet()) { others.add(new long[]{entry.getKey(), entry.getValue()}); } while (topX.size() < x && !others.isEmpty()) { long[] element = others.pollFirst(); topX.add(element); xSum += element[0] * element[1]; } answer[0] = xSum; for (int i = 1; i <= n - k; i++) { int outVal = nums[i - 1]; int inVal = nums[i + k - 1]; int outOldFreq = freqMap.get(outVal); if (topX.remove(new long[]{outVal, outOldFreq})) { xSum -= (long)outVal * outOldFreq; } else { others.remove(new long[]{outVal, outOldFreq}); } freqMap.put(outVal, outOldFreq - 1); if (outOldFreq - 1 > 0) { others.add(new long[]{outVal, outOldFreq - 1}); } else { freqMap.remove(outVal); } int inOldFreq = freqMap.getOrDefault(inVal, 0); if (inOldFreq > 0) { if (topX.remove(new long[]{inVal, inOldFreq})) { xSum -= (long)inVal * inOldFreq; } else { others.remove(new long[]{inVal, inOldFreq}); } } freqMap.put(inVal, inOldFreq + 1); others.add(new long[]{inVal, inOldFreq + 1}); while (topX.size() < x && !others.isEmpty()) { long[] toMove = others.pollFirst(); topX.add(toMove); xSum += toMove[0] * toMove[1]; } while (!topX.isEmpty() && !others.isEmpty() && comp.compare(topX.last(), others.first()) < 0) { long[] worstInTop = topX.pollLast(); long[] bestInOthers = others.pollFirst(); topX.add(bestInOthers); others.add(worstInTop); xSum -= worstInTop[0] * worstInTop[1]; xSum += bestInOthers[0] * bestInOthers[1]; } answer[i] = xSum; } return answer; } } ``` ### Algorithm * Define a custom `Comparator` for pairs of `(value, frequency)` that sorts by frequency (descending) and then value (descending). * Initialize a frequency map `freqMap`, a `TreeSet` `topX` (for top x elements), and a `TreeSet` `others` (for the rest), both using the custom comparator. * Initialize a `long` variable `xSum` to 0. * **Process the first window `nums[0...k-1]`**: Populate `freqMap`, then add all unique elements to `others`. Move the top `x` elements from `others` to `topX` and calculate the initial `xSum`. Store this in the `answer` array. * **Slide the window from `i = 1` to `n-k`**: * Let `outVal = nums[i-1]` and `inVal = nums[i+k-1]`. * **Handle `outVal`**: Decrement its frequency in `freqMap`. Remove its old entry from its set (`topX` or `others`). If it was in `topX`, update `xSum`. Add its new entry to `others` if its new frequency is positive. * **Handle `inVal`**: Increment its frequency in `freqMap`. Remove its old entry (if any) from its set. Add its new entry to `others`. * **Rebalance**: 1. If `topX` has fewer than `x` elements, move the best element from `others` to `topX`, updating `xSum`. 2. If the worst element in `topX` is 'smaller' than the best in `others`, swap them and update `xSum`. * Store the current `xSum` in the `answer` array. * Return `answer`. # Solutions ### Java ```java class Solution { private TreeSet < int []> l = new TreeSet <>(( a , b ) -> a [ 0 ] == b [ 0 ] ? a [ 1 ] - b [ 1 ] : a [ 0 ] - b [ 0 ]); private TreeSet < int []> r = new TreeSet <>( l . comparator ()); private Map < Integer , Integer > cnt = new HashMap <>(); private long s ; public long [] findXSum ( int [] nums , int k , int x ) { int n = nums . length ; long [] ans = new long [ n - k + 1 ]; for ( int i = 0 ; i < n ; ++ i ) { int v = nums [ i ]; remove ( v ); cnt . merge ( v , 1 , Integer: : sum ); add ( v ); int j = i - k + 1 ; if ( j < 0 ) { continue ; } while (! r . isEmpty () && l . size () < x ) { var p = r . pollLast (); s += 1L * p [ 0 ] * p [ 1 ]; l . add ( p ); } while ( l . size () > x ) { var p = l . pollFirst (); s -= 1L * p [ 0 ] * p [ 1 ]; r . add ( p ); } ans [ j ] = s ; remove ( nums [ j ]); cnt . merge ( nums [ j ], - 1 , Integer: : sum ); add ( nums [ j ]); } return ans ; } private void remove ( int v ) { if (! cnt . containsKey ( v )) { return ; } var p = new int [] { cnt . get ( v ), v }; if ( l . contains ( p )) { l . remove ( p ); s -= 1L * p [ 0 ] * p [ 1 ]; } else { r . remove ( p ); } } private void add ( int v ) { if (! cnt . containsKey ( v )) { return ; } var p = new int [] { cnt . get ( v ), v }; if (! l . isEmpty () && l . comparator (). compare ( l . first (), p ) < 0 ) { l . add ( p ); s += 1L * p [ 0 ] * p [ 1 ]; } else { r . add ( p ); } } } ``` ### CPP ```cpp class Solution { public: vector < long long > findXSum ( vector < int >& nums , int k , int x ) { using pii = pair < int , int > ; set < pii > l , r ; long long s = 0 ; unordered_map < int , int > cnt ; auto add = [ & ]( int v ) { if ( cnt [ v ] == 0 ) { return ; } pii p = { cnt [ v ], v }; if ( ! l . empty () && p > * l . begin ()) { s += 1LL * p . first * p . second ; l . insert ( p ); } else { r . insert ( p ); } }; auto remove = [ & ]( int v ) { if ( cnt [ v ] == 0 ) { return ; } pii p = { cnt [ v ], v }; auto it = l . find ( p ); if ( it != l . end ()) { s -= 1LL * p . first * p . second ; l . erase ( it ); } else { r . erase ( p ); } }; vector < long long > ans ; for ( int i = 0 ; i < nums . size (); ++ i ) { remove ( nums [ i ]); ++ cnt [ nums [ i ]]; add ( nums [ i ]); int j = i - k + 1 ; if ( j < 0 ) { continue ; } while ( ! r . empty () && l . size () < x ) { pii p = * r . rbegin (); s += 1LL * p . first * p . second ; r . erase ( p ); l . insert ( p ); } while ( l . size () > x ) { pii p = * l . begin (); s -= 1LL * p . first * p . second ; l . erase ( p ); r . insert ( p ); } ans . push_back ( s ); remove ( nums [ j ]); -- cnt [ nums [ j ]]; add ( nums [ j ]); } return ans ; } }; ``` ### Python ```python from sortedcontainers import SortedList class Solution : def findXSum ( self , nums : List [ int ], k : int , x : int ) -> List [ int ]: def add ( v : int ): if cnt [ v ] == 0 : return p = ( cnt [ v ], v ) if l and p > l [ 0 ]: nonlocal s s += p [ 0 ] * p [ 1 ] l . add ( p ) else : r . add ( p ) def remove ( v : int ): if cnt [ v ] == 0 : return p = ( cnt [ v ], v ) if p in l : nonlocal s s -= p [ 0 ] * p [ 1 ] l . remove ( p ) else : r . remove ( p ) l = SortedList () r = SortedList () cnt = Counter () s = 0 n = len ( nums ) ans = [ 0 ] * ( n - k + 1 ) for i , v in enumerate ( nums ): remove ( v ) cnt [ v ] += 1 add ( v ) j = i - k + 1 if j < 0 : continue while r and len ( l ) < x : p = r . pop () l . add ( p ) s += p [ 0 ] * p [ 1 ] while len ( l ) > x : p = l . pop ( 0 ) s -= p [ 0 ] * p [ 1 ] r . add ( p ) ans [ j ] = s remove ( nums [ j ]) cnt [ nums [ j ]] -= 1 add ( nums [ j ]) return ans ```