Easiest cpp Solution. Each step of the code is explained clearly🔥🔥
Intuition\n- The problem asks to find the maximum size of a subarray such that all the elements in the subarray can be made equal by performing at most k operat
# Intuition\n- The problem asks to find the maximum size of a subarray such that all the elements in the subarray can be made equal by performing at most k operations.\n- An operation is defined as incrementing or decrementing any element by one.\n- A possible intuition is to sort the array and then try to make all the elements in a subarray equal to the middle element of that subarray, as this would minimize the number of operations needed.\n- To check if a subarray of size len can be made equal with k operations, we can use a sliding window technique and calculate the number of operations needed for each window.\n\n# Approach\n- Sort the array in ascending order and store the prefix sum of the array in a vector.\n- Use binary search to find the maximum possible value of len, the size of the subarray, in the range [1, n].\n- For each value of len, use a helper function to check if there exists a subarray of size len that can be made equal with k operations.\n- The helper function uses a sliding window technique to iterate over all possible subarrays of size len and calculates the number of operations needed for each subarray using the prefix sum vector and the middle element of the subarray as the target value.\n- If the number of operations is less than or equal to k, return true. Otherwise, return false.\n- Return the maximum value of len that satisfies the helper function.\n\n# Complexity\n- The time complexity is $$O(n \\log n)$$, where n is the size of the array.\n- The sorting step takes $$O(n \\log n)$$ time.\n- The binary search takes $$O(\\log n)$$ time and each call to the helper function takes $$O(n)$$ time, so the total time for the binary search is $$O(n \\log n)$$.\n- Therefore, the overall time complexity is $$O(n \\log n)$$.\n\n# Space complexity:\n- The space complexity is $$O(n)$$, where n is the size of the array.\n- The prefix sum vector takes $$O(n)$$ space and the sorting step also takes $$O(n)$$ space in the worst case.\n- Therefore, the overall space complexity is $$O(n)$$.\n\n# Special Thanks to codestorywithMIK\n- You can refer [video](https://youtu.be/Iaz-8ZQYUvs?si=9nNMbuqrft4iho1L) for the solution. \n- Each step of the code is explained beautifully. \n\n\n# Code\n```\nclass Solution {\nprivate:\n    typedef long long ll;\n    bool isPossible(vector<int>& nums, ll k, int len, vector<ll>& prefixSum, int n) {\n        if (len == 0) return false;\n\n        int i = 0;\n        int j = len - 1;\n\n        while (j < n) {\n            ll target_idx = (i + j) >> 1;\n            ll target = nums[target_idx];\n\n            ll left_opr  = 0;\n            ll right_opr = 0;\n            \n            // Calculate the number of operations needed to make all elements on the left side of the target equal to the target\n            if (target_idx == 0) {\n                left_opr = 0;\n            }\n            else {\n                left_opr = abs( (target * (target_idx-i)) - (prefixSum[target_idx-1] - (i > 0 ? prefixSum[i - 1] : 0)) );\n            }\n\n            // Calculate the number of operations needed to make all elements on the right side of the target equal to the target\n            right_opr = abs( (target * (j - target_idx)) - (prefixSum[j] - prefixSum[target_idx]) );\n\n            // If the total number of operations is less than or equal to k, then it is possible to make all elements in the subarray of size \'len\' equal\n            if (left_opr + right_opr <= k) \n                return true;\n            \n            i ++;\n            j ++;\n        }\n\n        return false;\n    }\npublic:\n    int maxFrequencyScore(vector<int>& nums, long long k) {\n        int n = nums.size();\n\n        // Sort the array to make it easier to find the target number\n        sort(begin(nums), end(nums));\n\n        // Calculate the prefix sum of the array, which is helpful for calculating the number of operations in constant time\n        vector<ll> prefixSum(n, 0);\n        prefixSum[0] = nums[0];\n        for (int i = 1; i < n; i++) {\n            prefixSum[i] = prefixSum[i - 1] + nums[i];\n        }\n\n        // Apply binary search to find the maximum possible size of the subarray\n        int left  = 1; // minimum possible size of the subarray\n        int right = n; // maximum possible size of the subarray\n        int res   = 1; // initialize the result to 1, since every element is present at least once in the array\n\n        while (left <= right) {\n            int mid = (left + right) >> 1;\n\n            if (isPossible(nums, k, mid, prefixSum, n)) {\n                res  = mid;\n                left = mid + 1;\n            }\n            else {\n                right = mid - 1;\n            }\n        }\n\n        return res;\n    }\n};\n```
['Array', 'Binary Search', 'Sliding Window', 'Sorting', 'Prefix Sum', 'C++']