# Find X-Sum of All K-Long Subarrays I
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-x-sum-of-all-k-long-subarrays-i)
Canonical: https://scaleengineer.com/dsa/problems/find-x-sum-of-all-k-long-subarrays-i
**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:**

* `1 <= n == nums.length <= 50`
* `1 <= nums[i] <= 50`
* `1 <= x <= k <= nums.length`

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem. It iterates through each possible subarray of length `k`, and for each one, it calculates the x-sum independently. This method is straightforward to implement but is the least efficient due to redundant calculations for overlapping subarrays.
**Time:** O(n * k log k). The outer loop runs `n - k + 1` times (O(n)). Inside the loop, building the frequency map takes O(k). Sorting the distinct elements takes O(d log d), where `d` is the number of distinct elements (`d <= k`). In the worst case, this is O(k log k). Thus, the total complexity is O(n * k log k). · **Space:** O(n + k). We need O(n - k + 1) space for the answer array. Inside the loop, we use O(k) space for the frequency map and the list of entries, as there can be at most `k` distinct elements in a subarray of length `k`.
**Pros:** Simple to understand and implement.; Directly follows the logic from the problem description.; Sufficient for the given small constraints.
**Cons:** Highly inefficient for larger constraints as it recomputes frequencies and sorts for each subarray from scratch.; The time complexity has a factor of `k log k`, which can be slow if `k` is large.
### Explanation
The brute-force method involves a loop that iterates from the first possible subarray `nums[0...k-1]` to the last one `nums[n-k...n-1]`. In each iteration, we treat the current subarray as an independent problem.

For a given subarray, we first determine the frequency of each unique number it contains. A hash map is a suitable data structure for this. While counting frequencies, we can also compute the total sum of the subarray's elements. The problem states that if a subarray has fewer than `x` distinct elements, its x-sum is its total sum, so we handle this special case first.

If there are `x` or more distinct elements, we proceed to find the top `x` most frequent ones. To do this, we convert the frequency map into a list of (element, frequency) pairs and sort it. The sorting criteria are crucial: we sort primarily by frequency in descending order, and for elements with the same frequency, we sort by the element's value in descending order. After sorting, the first `x` items in the list are our top elements.

Finally, we calculate the x-sum by summing up all occurrences of these top `x` elements within the subarray. The result is stored, and the process repeats for the next subarray.

```java
import java.util.*;

class Solution {
    public int[] getXSum(int[] nums, int k, int x) {
        int n = nums.length;
        int[] answer = new int[n - k + 1];

        for (int i = 0; i <= n - k; i++) {
            answer[i] = calculateXSum(nums, i, i + k - 1, x);
        }
        return answer;
    }

    private int calculateXSum(int[] nums, int start, int end, int x) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        int totalSum = 0;
        for (int i = start; i <= end; i++) {
            int num = nums[i];
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
            totalSum += num;
        }

        if (freqMap.size() < x) {
            return totalSum;
        }

        List<Map.Entry<Integer, Integer>> entryList = new ArrayList<>(freqMap.entrySet());

        entryList.sort((a, b) -> {
            if (!a.getValue().equals(b.getValue())) {
                return b.getValue() - a.getValue(); // Descending frequency
            } else {
                return b.getKey() - a.getKey(); // Descending value
            }
        });

        Set<Integer> topXElements = new HashSet<>();
        for (int i = 0; i < x; i++) {
            topXElements.add(entryList.get(i).getKey());
        }

        int xSum = 0;
        for (int i = start; i <= end; i++) {
            if (topXElements.contains(nums[i])) {
                xSum += nums[i];
            }
        }
        return xSum;
    }
}
```
### Algorithm
- Iterate through each possible starting index `i` of a subarray, from `0` to `n - k`.
- For each `i`, consider the subarray from `nums[i]` to `nums[i + k - 1]`.
- Create a helper function `calculateXSum` that takes a subarray (or its start/end indices) and `x` as input.
- Inside `calculateXSum`:
  - Calculate the frequency of each element in the current subarray using a hash map.
  - Calculate the total sum of the subarray simultaneously.
  - If the number of distinct elements (i.e., `freqMap.size()`) is less than `x`, return the total sum.
  - Otherwise, convert the frequency map entries into a list.
  - Sort the list. The primary sort key is the frequency in descending order. The secondary sort key for tie-breaking is the element's value, also in descending order.
  - Create a set containing the top `x` elements from the sorted list for efficient lookup.
  - Iterate through the subarray again, and add an element to the `xSum` if it is present in the set of top `x` elements.
  - Return the final `xSum`.
- Store the result of `calculateXSum` for each `i` in the answer array.

## Sliding Window with Re-sorting
This approach improves upon the brute-force method by using a sliding window. Instead of re-calculating frequencies for each subarray from scratch, it maintains a frequency map for the current window and updates it as the window slides. This avoids redundant computations, though it still requires re-sorting the frequencies at each step.
**Time:** O(n * d log d). Initializing the first window takes O(k + d log d). Each of the `n - k` sliding steps involves updating the map (O(1)) and then sorting the `d` distinct elements (O(d log d)). Since the number of distinct elements `d` is at most 50, `d log d` is a small constant, making the effective time complexity O(n). · **Space:** O(n + d). O(n) for the output array. The frequency map and the list for sorting take O(d) space, where `d` is the number of distinct elements. Since `nums[i] <= 50`, `d` is at most 50, making this O(1) auxiliary space. Total space is dominated by the output array, O(n).
**Pros:** More efficient than brute force, especially if `k` is large.; Avoids rescanning the entire subarray to build frequencies at each step.; Time complexity is effectively linear in `n` given the problem's constraints on element values.
**Cons:** The re-sorting at each step is still a bottleneck, although it's performed on a smaller set of distinct elements (`d`) compared to `k`.; Implementation is slightly more complex than the brute-force approach.
### Explanation
The key insight for this optimization is that consecutive subarrays have a large overlap. When moving from `nums[i...i+k-1]` to `nums[i+1...i+k]`, only one element is removed (`nums[i]`) and one is added (`nums[i+k]`).

We start by processing the initial window (`nums[0...k-1]`) to get the first x-sum. We build its frequency map and calculate the x-sum just as in the brute-force approach. Then, we loop from `i = 1` to `n - k`.

In each step of the loop, we update the frequency map in O(1) time: decrement the count for `nums[i-1]` (the outgoing element) and increment the count for `nums[i+k-1]` (the incoming element). If an element's count drops to zero, we remove it from the map.

With the updated frequency map, we must find the new set of top `x` elements. We do this by converting the map's entries to a list and sorting it again based on the problem's criteria. Once the new top `x` elements are identified, we can calculate the new x-sum by iterating through these top `x` entries and summing up `value * frequency`. This sum is the answer for the current window.

```java
import java.util.*;

class Solution {
    public int[] getXSum(int[] nums, int k, int x) {
        int n = nums.length;
        int[] answer = new int[n - k + 1];
        Map<Integer, Integer> freqMap = new HashMap<>();

        // 1. Initialize the first window
        for (int i = 0; i < k; i++) {
            freqMap.put(nums[i], freqMap.getOrDefault(nums[i], 0) + 1);
        }
        answer[0] = calculateXSumFromMap(freqMap, x);

        // 2. Slide the window
        for (int i = 1; i <= n - k; i++) {
            // Remove the leftmost element
            int leftElement = nums[i - 1];
            freqMap.put(leftElement, freqMap.get(leftElement) - 1);
            if (freqMap.get(leftElement) == 0) {
                freqMap.remove(leftElement);
            }

            // Add the rightmost element
            int rightElement = nums[i + k - 1];
            freqMap.put(rightElement, freqMap.getOrDefault(rightElement, 0) + 1);

            // Recalculate x-sum for the new window
            answer[i] = calculateXSumFromMap(freqMap, x);
        }
        return answer;
    }

    private int calculateXSumFromMap(Map<Integer, Integer> freqMap, int x) {
        if (freqMap.size() < x) {
            int totalSum = 0;
            for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
                totalSum += entry.getKey() * entry.getValue();
            }
            return totalSum;
        }

        List<Map.Entry<Integer, Integer>> entryList = new ArrayList<>(freqMap.entrySet());

        entryList.sort((a, b) -> {
            if (!a.getValue().equals(b.getValue())) {
                return b.getValue() - a.getValue();
            } else {
                return b.getKey() - a.getKey();
            }
        });

        int xSum = 0;
        for (int i = 0; i < x; i++) {
            Map.Entry<Integer, Integer> entry = entryList.get(i);
            xSum += entry.getKey() * entry.getValue();
        }
        return xSum;
    }
}
```
### Algorithm
- Initialize a frequency map for the first window `nums[0...k-1]`.
- Calculate the x-sum for this first window by sorting its frequencies and store it in `answer[0]`.
- Iterate from `i = 1` to `n - k` to slide the window.
- In each iteration, update the frequency map by decrementing the count of the element leaving the window (`nums[i-1]`) and incrementing the count of the element entering the window (`nums[i+k-1]`).
- After updating the map, recalculate the x-sum for the new window's state.
- This recalculation involves converting the map to a list, sorting it, and summing the contributions of the new top `x` elements.
- Store the new x-sum in `answer[i]`.

# 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
  int s;
public
  int[] findXSum(int[] nums, int k, int x) {
    int n = nums.length;
    int[] ans = new int[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 += p[0] * p[1];
        l.add(p);
      }
      while (l.size() > x) {
        var p = l.pollFirst();
        s -= 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 -= 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 += p[0] * p[1];
    } else {
      r.add(p);
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> findXSum(vector<int> &nums, int k, int x) {
    using pii = pair<int, int>;
    set<pii> l, r;
    int 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 += 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 -= p.first * p.second;
        l.erase(it);
      } else {
        r.erase(p);
      }
    };
    vector<int> 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 += p.first * p.second;
        r.erase(p);
        l.insert(p);
      }
      while (l.size() > x) {
        pii p = *l.begin();
        s -= 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
```