Easy Explanation || C++ || O(n log n * log n) || ✅✅
Intuition\n Describe your first thoughts on how to solve this problem. \n# Step 1: Sorting the Input Vector\n\n\nsort(nums.begin(), nums.end());\n\nLogic:\n\n- 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n# Step 1: Sorting the Input Vector\n\n````\nsort(nums.begin(), nums.end());\n````\nLogic:\n\n- The input vector nums is sorted in ascending order.\n- Sorting is essential for the binary search and prefix sum calculations.\n\n# Step 2: Creating a Prefix Sum Vector\n\n```\nvector<long long> s(n + 1, 0);\nfor (i = 1; i <= n; i++) {\n    s[i] = s[i - 1] + nums[i - 1];\n}\n```\nLogic:\n\n- A prefix sum vector s is created to efficiently compute the sum of subarrays.\n- s[i] represents the sum of the first i elements of the sorted vector nums.\n- It helps in quickly calculating the sum of any subarray by subtracting two prefix sums.\n# Step 3: Binary Search for Maximum Frequency Score\n```\n\naa = 1;\nbb = n;\n\nwhile (aa < bb) {\n    cc = (aa + 1 + bb) / 2;\n\n    bool found = false;\n    for (i = 1; i + cc - 1 <= n; i++) {\n        long long l = i, r = i + cc - 1, m = (l + r) / 2, v = nums[m - 1];\n        x = (m - l + 1) * v - (s[m] - s[l - 1]) + (s[r] - s[m]) - (r - m) * v;\n        if (x <= k) {\n            found = true;\n            break;\n        }\n    }\n\n    if (found) {\n        aa = cc;\n    } else {\n        bb = cc - 1;\n    }\n}\n```\nLogic:\n\n- Binary search is performed to find the maximum frequency score within the given constraint k.\n- The search is conducted on the size of subarrays (cc).\n- The loop inside the binary search iterates over potential starting indices of subarrays.\n- For each starting index, it checks if the subarray satisfies the constraint x <= k.\n- If the constraint is met, it updates found to true, and the binary search adjusts the size of subarrays accordingly.\n# Step 4: Returning the Maximum Frequency Score\n\n```\nreturn aa;\n```\nLogic:\n\n- The function returns the size of the subarray (aa), which represents the maximum frequency score.\n# Example Usage\n\n```\nint main() {\n    Solution solution;\n    vector<long long> nums = {1, 2, 3, 4, 5};\n    long long k = 5;\n    int result = solution.maxFrequencyScore(nums, k);\n    cout << "Maximum Frequency Score: " << result << endl;\n    return 0;\n}\n```\nExample:\n\nFor the input vector {1, 2, 3, 4, 5} and constraint k = 5, the binary search finds that a subarray of size 2 satisfies the constraint.\n<!-- # Approach -->\n<!-- Describe your approach to solving the problem. -->\n\n# Time Complexity Analysis:\n\n- The dominant time complexity is the binary search loop which has a time complexity of O(n log n * log n).\n- Sorting the input vector and calculating the prefix sum both contribute O(n log n) to the overall time complexity.\n- The loop inside the binary search contributes O(n log n) as it iterates over the input vector.\n- The rest of the operations are constant time.\n# Space Complexity Analysis:\n\n- The dominant space complexity is due to the prefix sum vector \'s\', which has a space complexity of O(n).\n- The rest of the variables and vectors have constant space complexity (O(1)).\n- In summary, the overall time complexity is O(n log n * log n), and the overall space complexity is O(n). Keep in mind that the actual runtime may vary based on the specific characteristics of the input data.\n\n# Code\n```\n#include <iostream>\n#include <vector>\n#include <algorithm>\n\nusing namespace std;\n\nclass Solution {\npublic:\n    int maxFrequencyScore(vector<int>& nums, long long k) {\n        long long n = nums.size();\n        long long ans = 0, i, j, aa, bb, cc, x, curr;\n\n        // Time Complexity: O(n log n)\n        // Space Complexity: O(n)\n        sort(nums.begin(), nums.end());\n\n        // Time Complexity: O(n)\n        // Space Complexity: O(n)\n        vector<long long> s(n + 1, 0);\n        for (i = 1; i <= n; i++) {\n            s[i] = s[i - 1] + nums[i - 1];\n        }\n\n        // Time Complexity: O(n log n * log n)\n        // Space Complexity: O(1)\n        aa = 1;\n        bb = n;\n\n        while (aa < bb) {\n            cc = (aa + 1 + bb) / 2;\n\n            // Time Complexity: O(n * log n)\n            // Space Complexity: O(1)\n            bool found = false;\n            for (i = 1; i + cc - 1 <= n; i++) {\n                long long l = i, r = i + cc - 1, m = (l + r) / 2, v = nums[m - 1];\n                x = (m - l + 1) * v - (s[m] - s[l - 1]) + (s[r] - s[m]) - (r - m) * v;\n                if (x <= k) {\n                    found = true;\n                    break;\n                }\n            }\n\n            // Time Complexity: O(log n)\n            // Space Complexity: O(1)\n            if (found) {\n                aa = cc;\n            } else {\n                bb = cc - 1;\n            }\n        }\n\n        // Time Complexity: O(1)\n        // Space Complexity: O(1)\n        return aa;\n    }\n};\n\n// int main() {\n//     // Example usage\n//     Solution solution;\n//     vector<int> nums = {1, 2, 3, 4, 5};\n//     long long k = 5;\n\n//     // Time Complexity: O(n log n * log n)\n//     // Space Complexity: O(1)\n//     int result = solution.maxFrequencyScore(nums, k);\n\n//     cout << "Maximum Frequency Score: " << result << endl;\n\n//     return 0;\n// }\n\n```
['C++']