Find X-Sum of All K-Long Subarrays I

Easy
Watch on YouTube ↗

Solution

class Solution {

    HashMap<Integer, Integer> hmap;

    public int[] findXSum(int[] nums, int k, int x) {
        hmap = new HashMap<>();

        int n = nums.length;

        int ans[] = new int[n-k+1];
        int index = 0;

        for(int i=0; i<n; i++) {
            // O(n)*(logk(x+k))
            // O(k)

            hmap.put(nums[i], hmap.getOrDefault(nums[i], 0) + 1);

            if(i >= k-1) {
                ans[index++] = getSum(x);

                int removenum = nums[i-k+1];
                hmap.put(removenum, hmap.get(removenum)-1);
                if(hmap.get(removenum)==0) hmap.remove(removenum);
            }

        }
        return ans;
    }

    int getSum(int x) {
        int sum = 0;
        // klogk 
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> {
            {
                int f1 = hmap.get(a);
                int f2 = hmap.get(b);
                if(f1==f2) 
                    return b-a;
                return f2-f1;
            }
        });

        for(int key : hmap.keySet()) {
            pq.offer(key); 
        }
        // xlogk
        while(!pq.isEmpty() && x>0) {
            int top = pq.remove();
            sum += top*hmap.get(top);
            x--;
        }

        return sum;
    }
}