Find X-Sum of All K-Long Subarrays II

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.

• 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.

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.

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<Integer, Integer> freqMap = new HashMap<>();
            for (int j = i; j < i + k; j++) {
                freqMap.put(nums[j], freqMap.getOrDefault(nums[j], 0) + 1);
            }

            List<Map.Entry<Integer, Integer>> 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<Integer, Integer> entry = entries.get(j);
                currentXSum += (long) entry.getKey() * entry.getValue();
            }
            
            answer[i] = currentXSum;
        }
        return answer;
    }
}