Java sliding window with prefix sum
Intuition\n Describe your first thoughts on how to solve this problem. \n- We can compute the cost in constant time using the prefix sum (see the validate funct
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- We can compute the cost in constant time using the prefix sum (see the validate function).\n- We can use a binary search or a sliding window, I used a sliding window (see the sliding window function)\n- Don\'t forget to sort the array and compute the prefix sum at first.\n\n\n\n# Code\n```\nclass Solution {\n    public int maxFrequencyScore(int[] nums, long k) {\n        // Sort nums\n        // Prefix sum!\n        // Sliding window of valid, invalid sets\n        Arrays.sort(nums);\n        return slidingWindow(nums, k);\n    }\n\n    long[] prefixSum(int[] nums) {\n        int n = nums.length;\n        long[] ps = new long[n+1];\n        ps[0] = 0;\n        for (int i=0;i<n;i++) {\n            ps[i+1] = ps[i] + (long)nums[i];\n        }\n        return ps;\n    }\n\n    int slidingWindow(int[] nums, long k) {\n        long[] ps = prefixSum(nums);\n        int start = 0;\n        int end = 1;\n        int maxFreq = 1;\n        int n = nums.length;\n        while (end <= n) {\n            boolean valid = validate(nums, start, end, k, ps);\n            if (valid) {\n                int freq = end - start;\n                maxFreq = Math.max(maxFreq, freq);\n                end++;\n            } else {\n                start++;\n            }\n        }\n        return maxFreq;\n    }\n\n    boolean validate(int[] nums, int start, int end, long k, long[] ps) {\n        if (start >= end - 1) {\n            return true;\n        }\n        int mid = (start + end) / 2;\n        // target is the median\n        long target = nums[mid];\n        int n = nums.length;\n        long cost = target * ((long)(2*mid-end-start)) + ps[end] + ps[start] - ps[mid] - ps[mid];\n        boolean validate = (cost <= k);\n        return validate;\n    }\n}\n```
['Java']