Video Explanation (All the approaches with intuitions)
Explanation\n\nClick here for the video\n\n# Code\n\n## Lower Middle Element as median\n\ntypedef long long int ll;\n\nclass Solution {\n    \n    bool IsPossib
# Explanation\n\n[Click here for the video](https://youtu.be/BPYnR2PwzVE)\n\n# Code\n\n## Lower Middle Element as median\n```\ntypedef long long int ll;\n\nclass Solution {\n    \n    bool IsPossible (int len, const vector<int>& arr, const ll K) {\n        int n = arr.size();\n        if (len > n) return false;\n        \n        vector<ll> prefix(n+1, 0);\n        for (int j = 1; j <= n; j ++) prefix[j] = prefix[j-1] + arr[j-1];\n        \n        for (ll l = 1, r = len; r <= n; l ++, r ++) {\n            ll median = (l+r) >> 1;\n            ll val = arr[median-1];\n            \n            ll less_to_median = (median - l + 1)*val - (prefix[median] - prefix[l-1]);\n            ll more_to_median = r <= median? 0 : (prefix[r] - prefix[median]) - (r - median)*val;\n                        \n            if ((less_to_median + more_to_median) <= K) return true;\n        }\n        \n        return false;\n    }\n    \npublic:\n    int maxFrequencyScore(vector<int>& nums, long long k) {\n        int n = nums.size();\n        sort (nums.begin(), nums.end());\n        \n        int l = 1, r = n;\n        while (l < r) {\n            int m = (l+r) >> 1;\n            \n            if (IsPossible(m+1, nums, k)) l = m+1;\n            else r = m;\n        }\n        return l;\n    }\n};\n```\n\n## Higher Middle Element as median\n```\ntypedef long long int ll;\n\nclass Solution {\n    \n    bool IsPossible (int len, const vector<int>& arr, const ll K) {\n        int n = arr.size();\n        if (len > n) return false;\n        \n        vector<ll> prefix(n+1, 0);\n        for (int j = 1; j <= n; j ++) prefix[j] = prefix[j-1] + arr[j-1];\n        \n        for (ll l = 1, r = len; r <= n; l ++, r ++) {\n            ll median = (l+r) >> 1;\n            if ((r - l + 1) % 2 == 0) median ++;\n            \n            ll val = arr[median-1];\n            \n            ll less_to_median = (median - l + 1)*val - (prefix[median] - prefix[l-1]);\n            ll more_to_median = r <= median? 0 : (prefix[r] - prefix[median]) - (r - median)*val;\n                        \n            if ((less_to_median + more_to_median) <= K) return true;\n        }\n        \n        return false;\n    }\n    \npublic:\n    int maxFrequencyScore(vector<int>& nums, long long k) {\n        int n = nums.size();\n        sort (nums.begin(), nums.end());\n        \n        int l = 1, r = n;\n        while (l < r) {\n            int m = (l+r) >> 1;\n            \n            if (IsPossible(m+1, nums, k)) l = m+1;\n            else r = m;\n        }\n        return l;\n    }\n};\n```
['C++']