C++ || Sliding window || medium explanation
I write this solution with reference to lee215\'s solution. There\'re no difference but I want to explain more about how it works. It tooks me one day to unders
I write this solution with reference to lee215\'s solution. There\'re no difference but I want to explain more about how it works. It tooks me one day to understand it.\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSort the input array: We need to find the longest subsequence of array which can be changed to a unique value with the cost not higher than k. To reduce the cost, those numbers in the subsequence must be as close as possible. Therefore, we must sort the input array. Now we only need to find the longest subarray which satisfies the above condition.\n\nThe minimum cost: Given a subarray, the cost is minimum if we pick the medium of subarray as the target.\n# Explanation\n<!-- Describe your approach to solving the problem. -->\n## Why it\'s medium\nLet\'s check some basic cases:\n### Subarray having only two numbers:\nSolving the basic problem a subarray having only two numbers will reveal an interest thing.\n\nFor example, we have this subarray [2, 6]. Following graph shows the costs for all targets in range [0, 10]\n![chart.png](https://assets.leetcode.com/users/images/fe4b59ef-51ff-47e3-8f9b-6c8e9f89e07b_1703338597.4837976.png)\n\n\n\n  \nThe cost is minimum if we pick the target in range [2, 6].\n\n### Subarray with an even length:\n\nnums = [A0, A1, A2, A3, A4, A5]\n\n\nLet\'s define a function cost(i, j, target) is the cost to change i and j to the target and\ncost(target) is the cost to change all numbers in nums to the target.\n\nInstead of changing each number, we will changing a pair of numbers to the target: [A0, A5], [A1, A4], [A2, A3]\n```\ncost(target) = cost(A0, A5, target) + cost(A1, A4, target) + cost(A2, A3, target)\n```\n\nBase on the previous observation, if the target is in range [A0, A5], the value of cost(0, 5, target) is minimum (let\'s call it min_cost(0, 5, target)).\nIf we pick the target in range [A2, A3], the cost will be minimum:\n```\ncost(target) = min_cost(A0, A5, target) + min_cost(A1, A4, target) + min_cost(A2, A3, target)   for target in [A2, A3]\n```\n\nIn this case, we don\'t have to pick the medium as the target we can pick any number in range [A2, A3] as the target.\n\n  \n\n### Subarray with an odd length:\n\n\nnums = [A0, A1, A2, A3, A4, A5, A6]\n\nIt\'s similar to the previous problem, we will group numbers to pairs: [A0, A6], [A1, A5], [A2, A4] and leave A3 alone.\nWe can only pick the medium A3 as the target because if we pick any other number in range [A2, A4], we will need an extra cost to change A3 to that target.\n\n## Sliding window:\n\nIt\'s time to calculate that minimum cost.\n\n- Let\'s check how we extend the window by one number:\n\n|window \t|[A0]\t|[A0, A1]  \t|[A0, A1, A2]\t\t\t|[A0, A1, A2, A3]\t\t|\n| --------- | ----- | --------- | --------------------- | --------------------- |\n|target \t|A0\t\t|A0\t\t\t|A1\t\t\t\t\t\t|A1\t\t\t\t\t\t|\n|cost \t\t|0  \t|A1 - A0\t|A2 - A0\t\t\t\t|A3 + A2 - A1 - A0\t\t|\n|cost \t\t|0  \t|A1 - A0\t|(A1- A0) + (A2 - A1)\t|(A2 - A0) + (A3 - A1)\t|\n\nEach time we add a number Ai the cost will increase (Ai - target). The target is the one after adding a number Ai.\n- This is the cost to remove a number from window:\n\n|window \t|[A0, A1, A2, A3]\t|[A1, A2, A3]\t\t\t\t\t\t|[A2, A3]           |[A3]|\n| --------- | ----------------- | --------------------------------- | ----------------- | --------------------- |\n|target \t|A1\t\t\t\t\t|A2\t\t\t\t\t\t\t\t\t|A2\t\t\t\t\t|A3\t|\n|cost \t|A3 + A2 - A1 - A0  \t|A3 - A1\t\t\t\t\t\t\t\t|A3 - A2\t\t|0|\n|cost \t|A3 + A2 - A1 - A0 \t|(A3 + A2 - A1 - A0) - (A2 - A0) \t|(A3 - A1) - (A2 - A1)\t|(A3 - A2) - (A3 - A2)|\n\nEach time we remove a number Ai, the cost will decrease (target - Ai). The target is the one after removing a number Ai.\n\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n# Code\n```\nclass Solution {\npublic:\n    int maxFrequencyScore(vector<int>& nums, long long k) {\n        // Sliding window and medium\n        long long cost = 0;\n        int left = 0;\n        int max_score = 1;\n        sort(nums.begin(), nums.end());\n        for (int right = 0; right < nums.size(); right++)\n        {\n            cost += nums[right] - nums[(left + right) / 2];\n            while (cost > k)\n            {\n                cost += nums[left] - nums[(left + right + 1) / 2];\n                left++;\n            }\n            max_score = max(max_score, right - left + 1);\n        }\n        return max_score;\n    }\n};\n```
['Sliding Window', 'C++']