C++, slide window
Intuition\n Describe your first thoughts on how to solve this problem. \nIntuition is using a sliding window to track the valid range, making it possible to app
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIntuition is using a sliding window to track the valid range, making it possible to apply a template\n\n```C++ []\nwhile (right < n)\n{\n    while (!valid)\n    {\n        left++;\n    }\n    right++;\n}\n```\nSo the question boils down to how to determine if a range of numbers can be considered valid within a given threshold k.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nUsing the median to flatten a range of numbers, a simple approach would be:\n\n```C++ []\nint res = 0;\nfor (int i = left; i <= right; i++)\n    res += abs(median - nums[i]);\n```\nThis would result in a time complexity of:\nN\xD7(N\xD7(right\u2212left+1)).\n\n\nUsing the prefix to simplify the above process, apply the same logic as in the above code: find the sum before the midpoint and after the midpoint, then flatten it.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(N)\n# Code\n```\nclass Solution {\npublic:\n    \n    bool helper(vector<int>& nums, long long k, int left, int right, vector<long long>& preFix)\n    {\n        if (right >= nums.size())\n            return false;\n        else if (left == right)\n            return true;\n\n        long long idx    = (left + right) / 2;\n        long long mid    = nums[idx];\n\n        long long aftSum = preFix[right] + nums[right] - preFix[idx+1];\n        long long preSum = preFix[idx] - preFix[left];\n        long long res    = 0;\n\n        if (preSum != 0)\n            res += abs((mid*(idx - left)) - preSum);\n        if (aftSum != 0)\n            res += abs((mid*(right - idx)) - aftSum);\n\n        return (res <= k);\n    }\n\n    int maxFrequencyScore(vector<int>& nums, long long k) {\n        sort(nums.begin(), nums.end());\n        int n = nums.size();\n\n        vector<long long> preFix(n, 0);\n\n        for (int i = 1; i < n; i++)\n        {\n            preFix[i] = preFix[i-1] + nums[i-1];\n        }\n        \n        int left  = 0;\n        int right = 0;\n        int res   = 0;\n        while (right < n)\n        {\n            while (!helper(nums, k, left, right, preFix))\n            {\n                left++;\n            }\n\n            int length = right - left + 1;\n            res = max(res, length);\n            right++;\n        }\n        \n        return res;\n    }\n};\n```
['C++']