🚀 Brutal Brute Force || Java || O(n) || Sliding Window || No built-ins! ||Easy 🎉
Intuition\uD83E\uDDE0\nThe problem involves calculating the x-sum of all k-long subarrays of the input array. The x-sum considers the most frequent elements in 
# Intuition\uD83E\uDDE0\nThe problem involves calculating the x-sum of all k-long subarrays of the input array. The x-sum considers the most frequent elements in a subarray, allowing us to track the top x most frequent elements and their counts efficiently using a **sliding window technique**.\n\n---\n\n\n# Approach\uD83D\uDEE0\uFE0F\n**Step-by-Step Breakdown \uD83D\uDD0D:**\n\n**Sliding Window Technique \uD83D\uDD04:**\nMaintain a window of size k over the array and slide it one element at a time.\nUse an array freq to count the occurrences of each number in the current window, where freq[i] represents the count of the number i.\nInitial Setup \uD83C\uDFC1:\nStart with a window containing the first k elements and populate the freq array with their counts.\nCalculate the x-sum for this initial window using a helper function find.\n\n**Window Sliding \uD83D\uDD00:**\nSlide the window to the right, updating the freq array by adding the new rightmost element and removing the leftmost element as the window shifts.\nRecompute the x-sum for each new window and store the result.\n\n**Helper Function `find` \uD83C\uDFAF Explanation:**\n\n- *Deep Copy Creation \uD83D\uDCDD:*\n  - A copy of the original frequency array `f` is created to preserve the original counts for the subsequent sliding windows.\n  - Two arrays are used: `freq` to store the frequencies and `nums` to store the corresponding values (from 1 to 50). This setup maintains the **mapping between numbers and their frequencies**.\n\n- *Sorting (**Insertion Sort**) \uD83D\uDCCA:*\n  - The goal is to sort the `freq` array in descending order while keeping the corresponding numbers in the `nums` array synchronized.\n  - This is achieved using an insertion sort:\n    - For each element in the `freq` array, compare it with previous elements and shift higher frequency values to the right until the correct position for the current frequency (`key`) is found.\n    - Simultaneously, the `nums` array is updated to maintain the `freq:value` pair order.\n\n- *Handling Ties Between Frequencies \u2696\uFE0F:*\n  - If two elements have the same frequency, the sorting algorithm correctly places the higher-valued element first. This happens because the `nums` array is initially filled in ascending order (1 to 50), ensuring that when frequencies are equal, the value being considered in the insertion sort will always be larger than the previous one.\n  - Thus, the algorithm naturally satisfies the condition where higher values are treated as more frequent when there is a tie in frequency.\n\n- *Calculating the X-Sum \uD83E\uDDEE:*\n  - After sorting, the first `x` elements in the `nums` array correspond to the numbers with the highest frequencies.\n  - For each of these top `x` numbers, their frequency is multiplied by the value itself, and the result is added to the sum.\n\n---\n\n\n# Complexity\uD83D\uDCCA\n- **Time complexity:**\n**Sliding Window Initialization:** Filling the frequency array for the first window takes O(k).\n**Sliding Window Update:** For each of the n - k remaining windows, updating the frequency array takes O(1).\n**Sorting in find Function:** Sorting the frequency array has a time complexity of O(51 log 51), which is effectively O(1) due to the fixed size of 51.\nAlthough each subarray\'s processing seems like O(k), the fixed frequency array length (51) allows sorting and finding the top x elements in constant time, making the overall complexity O(n).\n\n**Final Time Complexity: O(n)**\n- **Space complexity:**\n**Frequency Array:** Uses O(51) space, which is effectively O(1).\n**Result Array:** Uses O(n - k + 1) space.\n\n**Final Space Complexity: O(n)**\n\n---\n\n\n# Code (with detailed comments)\n```java []\nclass Solution {\n    public int[] findXSum(int[] nums, int k, int x) {\n        int[] ans=new int[nums.length-k+1];\n        \n        int left=0;\n        int right=k-1;\n        int[] freq= new int[51]; //for storing the count\n        for(int i=left;i<=right;i++)freq[nums[i]]++; //counted\n        ans[0]=find(freq,x); //firstSubArray\'sAnswer\n        \n        int ind=1; //ans array pointer\n        while(right<nums.length){\n            right++; //next one in the array\n            if(right==nums.length)break; //if reached out break\n            freq[nums[right]]++; //count the incoming number\n            freq[nums[left]]--; //decrement left most number\'s count\n            left++; //update left\n            \n            ans[ind++]=find(freq,x); //find the top x for this freq\n        }\n        return(ans);\n    }\n    private int find(int[] f, int x){\n        //create a deep copy of f as f needs to be preserved for next subarrays\n        int[] freq= new int[51]; \n        for(int i=0;i<51;i++) freq[i]=f[i]; //done\n        int[] nums=new int[51];\n        for(int i=0;i<51;i++)nums[i]=i; //we need a freq:value pointer, hence this array\n\n        //perform any sort (used insertion below) on freq to be descending\n        //while modifying freq modify corresponding num as well in the nums array\n        //so the freq:value pair order is preserved\n        for(int i=1;i<51;i++){\n            int key=freq[i];\n            int numKey=nums[i];\n            int j=i-1;\n            while(j>=0 && freq[j]<=key){\n                freq[j+1]=freq[j];\n                nums[j+1]=nums[j];\n                j--;\n            }\n            freq[j+1]=key;\n            nums[j+1]=numKey;\n        }\n        //in the end we get the descending order of the freq\n        //along with which number\'s freq each is\n        int sum=0;\n        for(int i=0;i<x;i++){ //simply calculate the sum of numbers upto x elements\n            sum+=(nums[i]*freq[i]); //each i in nums have repeated freq[i] times, so add that\n        }\n        return(sum);\n    }\n}\n```\n\n---\n\n![itachi_sad_upvote.jpg](https://assets.leetcode.com/users/images/72f7adcd-adc3-4058-9f69-fe9df736734e_1728792835.1081.jpeg)\n
['Sliding Window', 'Sorting', 'Java']