JAVA | Sliding Windows for large N
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {
    // record won't help as we need to incr/decr freq
    class Pair {
        int num;
        int freq;
        public Pair(int num, int freq) {
            this.num = num;
            this.freq = freq;
        }
    }

    public int[] findXSum(int[] nums, int k, int x) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        
        // Map to quickly access the Pair for a given number.
        Map<Integer, Pair> numToPairMap = new HashMap<>();
        
        // TreeSet to maintain ordering of pairs.
        // Sorted by frequency descending, then by number descending.
        TreeSet<Pair> tree = new TreeSet<>((a, b) -> {
            if (a.freq!=b.freq) return b.freq - a.freq; // higher frequency first
            if (a.num!=b.num) return b.num-a.num;     // higher number first when frequencies tie
            return 0;
        });
        
        int i=0,j=0;
        while(j<n){
            Pair inPair = numToPairMap.get(nums[j]);
            if(inPair == null){
                inPair = new Pair(nums[j],1);
                tree.add(inPair);
                numToPairMap.put(nums[j], inPair);
            }else{
                tree.remove(inPair);
                inPair.freq++;
                tree.add(inPair);
            }
            if(j-i+1 == k){
                res[i] = computeXSum(tree, x);
                // remove ith num
                Pair outPair = numToPairMap.get(nums[i]);
                tree.remove(outPair);
                outPair.freq--;
                if(outPair.freq > 0 ) { tree.add(outPair);}
                i++;
                j++;
            }else{
                j++;
            }
        }
        return res;
    }
    
    // Helper method to compute the x-sum for the current window based on the TreeSet.
    private int computeXSum(TreeSet<Pair> tree, int x) {
        int sum = 0, count = 0;
        // Since our TreeSet is sorted by frequency (then value) in descending order,
        // iterating over it will give the highest frequency numbers first.
        for (Pair p : tree) {
            if (count < x) {
                sum += p.num * p.freq;
                count++;
            } else {
                break;
            }
        }
        return sum;
    }
}

```
['Java']